剑指offer最优解Java版-二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

第一种思路：二分查找

把每一行看成有序递增的数组，
利用二分查找，
通过遍历每一行得到答案，
时间复杂度是nlogn

public boolean Find(int [][] array,int target) {
         
        for(int i=0;i<array.length;i++){
            int low=0;
            int high=array[i].length-1;
            while(low<=high){
                int mid=(low+high)/2;
                if(target>array[i][mid])
                    low=mid+1;
                else if(target<array[i][mid])
                    high=mid-1;
                else
                    return true;
            }
        }
        return false;
    }

复杂度分析：

• 时间复杂度：O(nlogn)。 每一行查找时间复杂度O(logn)，n行
• 空间复杂度：O(1)

第二种思路

利用二维数组由上到下，由左到右递增的规律，那么选取右上角或者左下角的元素a[row][col]与target进行比较：
当target小于元素a[row][col]时，那么target必定在元素a所在行的左边，即col--；
当target大于元素a[row][col]时，那么target必定在元素a所在列的下边，即row++。

之所以不选择左上角或者右下角，是因为位移路径不唯一。

class Solution {
    public static boolean Find(int target, int [][] array) {
        int length = array[0].length;
        int col = length - 1;
        int row = 0;
        while (col >= 0 && row < length) {
            if (array[row][col] == target) {
                return true;
            } else {
                if (array[row][col] < target) {
                    row++;
                    continue;
                }
                if (array[row][col] > target) {
                    col--;
                    continue;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[][] nums = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        System.out.println(Find(7, nums));
    }

}

复杂度分析：

• 时间复杂度：O(n)。我们只遍历了矩阵长度n相关的次数，即可找到答案
• 空间复杂度：O(1)

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我