剑指 Offer 04. 二维数组中的查找

题目描述

在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
现有矩阵 matrix 如下：
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
题目链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof

思路

二分查找，目标值在当前行数组的范围内就进行二分查找

实现代码 

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n  = matrix.length;
        if(n == 0) {
            return false;
        }
        for(int i = 0; i < n; i++){
            int m = matrix[i].length;
            if(m > 0 && target >= matrix[i][0] && target <= matrix[i][m - 1]){
                //目标值在当前行数组的范围内就进行二分查找
                if(binarySearch(matrix[i], target)){
                    return true;
                }
            }
        }
        return false;
    }
    public boolean binarySearch(int[] arr, int target){ //二分查找
        int left = 0;
        int right = arr.length - 1;
        int mid = 0;
        while(left <= right){
            mid = left + (right - left) / 2;
            if(arr[mid] == target){
                return true;
            }else if(arr[mid] < target){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return false;
    }
}

剑指 Offer 11. 旋转数组的最小数字

题目描述

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。  
输入：[3,4,5,1,2]
输出：1
题目链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

方法一：暴力解法

直接遍历，因为数组没旋转之前为递增的，所以找到第一个当前元素小于前一个元素的位置，即为旋转数组的最小值 
class Solution {
    public int findMin(int[] nums) {
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < nums[i-1]){
                return nums[i];
            }
        }
        //没有旋转第一个元素就为最小值
        return nums[0];
    }
}

方法二：二分法

思路

数组中最特殊的位置是左边位置left和右边位置right，将它们与中间位置mid的值进行比较，进而判断最小数字出现在哪里。
  • 左边有序数组是大于等于右边有序数组的
  • 当 nums[mid] < nums[right] 时，可知最小值在左边有序数组，但 mid 有可能是最小值，下一轮搜索区间是 [left, mid]
  • 当 nums[mid] > nums[right] 时，可知最小值在右边有序数组，下一轮搜索区间是 [mid + 1, right]
  • 当 nums[mid] = nums[right] 时，无法确定最小值在哪边，但可知无论nums[right]是否为最小值都有替代者，因此可通过缩小边界忽略该右端点
用左边位置left和中间位置mid的值进行比较是否可以？
举例：[3, 4, 5, 1, 2] 与 [1, 2, 3, 4, 5] ，此时，中间位置的值都比左边大，但最小值一个在后面，一个在前面，因此这种做法不能有效地减治。 
class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (numbers[mid] < numbers[right]) { //最小值在左边，mid位置也有可能是最小值
                right = mid;
            } else if (numbers[mid] > numbers[right]) { //最小值在右边
                left = mid + 1;
            } else { //相等就缩小右边界
                right -= 1;
            }
        }
        return numbers[left];
    }
}

剑指 Offer 50. 第一个只出现一次的字符

题目描述

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
输入：s = "abaccdeff"
输出：'b'

方法一：有序哈希

目的是找出第一个只出现一次的字符，使用LinkedHashMap保证插入的顺序 
class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            int val = map.getOrDefault(c, 0);
            map.put(c, val + 1);
        }
        for(char key : map.keySet()){
            if(map.get(key) == 1){
                return key;
            }
        }
        return ' ';
    }
}