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

剑指offer:04. 二维数组中的查找,第1张

04. 二维数组中的查找

来源:力扣(LeetCode)

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

在一个 n ∗ m n * m nm 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。


请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。


示例:

现有矩阵 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)

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/563346.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存