leetcode剑指Offer第五天

二维数组中的查找

在一个 n * m 的二维数组中，每一行都按照从左到右非递减的顺序排序，每一列都按照从上到下非递减的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例：

现有数组：
[
  [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。

限制：

0 <= n <= 1000
0 <= m <= 1000

解题思路

在遍历数组时，需要注意遍历顺序和要求，如本题而言，如果总左上角开始遍历，你会发现其左侧和下侧都是大于本数，是一种暴力遍历

但是如果从右上角开始遍历，你会发现其左侧是小于自己的数，下面是大于自己的数，这就将数组划为了两个部分，取满足条件的一端能更快的搜到数据

Java代码

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}

旋转数组的最小数字

Easy 原题连接：旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。

给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。

注意，数组 [a[0], a[1], a[2], …, a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], …, a[n-2]] 。

示例：

输入：numbers = [3,4,5,1,2]
输出：1
输入：numbers = [2,2,2,0,1]
输出：0

提示：

n == numbers.length
1 <= n <= 5000
-5000 <= numbers[i] <= 5000
numbers 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

解题思路

二分 + 斜率判断

因为进行了1 - n次旋转，所以在数组中间（而非两端）一定存在一个“断点”，以这个断点作为二分查找的要素查找即可

Java代码

class Solution {
    public int minArray(int[] numbers) {
        //对于数组最右侧的数字a来说，最小值右侧数据一定小于a，最小值左侧数据一定大于a
        //1.利用双指针指向首尾，并依次取出中间值与尾数值比较
        //2.中间值大于尾数值：最小值位于中间值右侧，首指针指向中间值
        //3.中间值小于尾指针，最小值位于中间值左侧, 尾指针指向中间值
        //4.中间值等于尾指针，不可确定，将尾指针前移一位再做判断
        if(numbers.length == 1) return numbers[0];

        int first = 0, last = numbers.length-1;
        while(last > first) {
            int mid = first + (last - first)/2;
            if(numbers[last]>numbers[mid]) {
                last = mid;
            }else if(numbers[last]<numbers[mid]) {
                first = mid+1;
            }else {
                last--;
            }
        }
        return numbers[first];
    }
}

第一个只出现一次的字符

Easy 原题连接：第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例：

输入：s = "abaccdeff"
输出：'b'
输入：s = "" 
输出：' '

限制：

0 <= s 的长度 <= 50000

解题思路

题目比较死板，总字符也就26个，暴力算了

Java代码



class Solution {
    public char firstUniqChar(String s) {
        // ---- 方法一 ----
        int[] fin = new int[26];
        char[] strs = s.toCharArray();
        if(strs.length == 0) return ' ';
        for(char i : strs)fin[i - 'a']++;
        for(char i : strs){
            if(fin[i-'a']==1)return i;
        }
        return ' ';

        // ---- 方法二 ----
        // char[] strs = s.toCharArray();
        // int[] flag = new int[strs.length];
        // if(strs.length == 0) return ' ';
        // char thisIs = strs[0];
        // for(int i = 0; i<strs.length; i++){
        //     if(flag[i] == 1)continue;
        //     for(int j=i+1; j<strs.length; j++){
        //         if(strs[i] == strs[j]){
        //             flag[i] = 1;
        //             flag[j] = 1;
        //         }
        //     }
        // }
        // for(int i=0; i<flag.length; i++){
        //     if(flag[i]==0)return strs[i];
        // }
        // return ' ';
    }
}