剑指offer 二维数组中的查找java实现

2020/12/14 23:46: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。

限制:0 <= n <= 1000
	 0 <= m <= 1000

leetcode:https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

解题思路

对于该二维数组,每一行都从左到右递增,每一列都从上到下递增;所以对于该数组中的一个数,小于它的数一定在其左边,大于它的数一定在其下边。从右上角开始查找,根据 target 和当前元素的大小关系来快速地缩小查找区间(每次排除一行或一列),每次减少一行或者一列的元素。当前元素的查找区间为该元素左下角的所有元素。

例如target = 16; 16 > 15; 排除第一行, 19 > 16; 排除第五列, 12 < 16; 排除第二行, 16 == 16; 找到了,返回true 

代码

class Solution {
   
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
   
        boolean found = false;
        //此处当matrix为[]时,会报错:java.lang.ArrayIndexOutOfBoundsException: Index 0 out of bounds for length 0
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
   
            return found;
        }
        int rows = matrix.length;
        int columns = matrix[0].length;
        int row = 0, column = columns - 1;
        for(;row < rows && column >= 0;){
   
            if(matrix[row][column] == target){
   
                found = true;
                break;
            }
            else if(matrix[row][column] > target){
   
                column--;
            }
            else{
   
                row++;
            }
        }
        return found;
    }
}