剑指01.二维数组中的查找

题目描述

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

案例

输入：7，返回true ； 输入5， 返回false

 方法1：暴力法

public class Solution {
    public boolean Find(int target, int [][] array) {
        //判断数组是否为空
        if(array.length == 0 || array[0].length == 0) return false;
        for (int i = 0; i < array.length; i++){
            for (int j = 0; j < array[0].length; j++){
                if (array[i][j] == target){
                    return true;
                }
            }
        }
        return false;
    }
}

时间复杂度：O(n^2)，因为最坏情况下，数组中的元素都需要遍历一次。
空间复杂度：O(1)

方法2：从右上找

public class Solution {
    public boolean Find(int target, int [][] array) {
        //每次取右上角的数字，与target进行对比
        //如果该数字大于target，则剔除这个数字所在的列
        //如果该数字小于target，则剔除这个数字所在的行
        int rows = array.length;       //一共有多少行
        int columns = array[0].length; //一共有多少列
        if (rows == 0 || columns == 0) return false; //判断数组是否为空
        int row = 0;
        int col = columns - 1;
        while (row < rows && col >= 0 ){
            if (array[row][col] > target){
                col--;
            }else if (array[row][col] < target){
                row++;
            }else
                return true;
        }
        return false;
    }
}

时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
空间复杂度：O(1)