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

04. 二维数组中的查找

来源：力扣（LeetCode）

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

在一个 n ∗ m n * m 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

解题思路：

• 利用从左到右有序增大，从上到下有序增大查找；以每行最右上角元素进行比较，判断属于哪一层哪一列；如果最右上角元素比目标值大，则表明在左下角的元素中，列数-1；如果目标值比最右上角元素要大，则行数+1；也可以先找到属于某一行，再在某一层之后进行顺序查找或者二分查找；但还是不如第一种方法逐渐缩小比较范围更好；

代码实现

• python实现

class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        rows = len(matrix)
        if rows == 0:
            return False
        cols = len(matrix[0])
        if cols == 0:
            return False
        row = 0
        col = cols - 1
        while row < rows and col >= 0:
            refer_num = matrix[row][col]
            if refer_num == target:
                return True
            elif refer_num > target:
                col -= 1
            else:
                row += 1
        return False

• c++实现

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int rows = matrix.size();
        if(rows==0)
            return false; 
        int cols = matrix[0].size();
        if(cols==0)
            return false;

        int row = 0;
        int col = cols-1;
        while(row < rows && col >= 0)
        {
            int refer_num = matrix[row][col];
            if(refer_num==target)
            {
                return true;
            }
            else if(refer_num < target)
            {
                row++;
            }
            else
            {
                col--;
            }
        }
        return false;
    }
};

复杂度分析

• 时间复杂度： O ( m + n ) O(m+n) O(m+n)
• 空间复杂度： O ( 1 ) O(1) O(1)