提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

二维数组中的查找

数组
2023-04-18 15:21:57 时间

问题：矩阵从左至右、从上至下非递减 顺序，查找target是否在数组中剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode）

方法一：标志数flag：选择左下角或者右上角为标志数；

选择左下角为flag：若flag > target，则target在flag所在行的上方，那么此行向前递减；若flag < target，则target在flag所在列的右方，那么此列进行递增；

时间复杂度：O(M+N)；空间复杂度：O(1);

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int i = matrix.size()-1, j =0;
        while(i >= 0 && j < matrix[0].size()){
            if(matrix[i][j] > target) --i;
            else if(matrix[i][j] < target) ++j;
            else 
                return true;
        }
        return false;
    }
};

 方法二：二分查找

标准库中的 lower_bound(first，last，target) 函数，对每一行进行一次二分查找；返回不小于等于target的迭代器

该函数要求范围内的数有序，至少针对target已经进行了划分。

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(const auto& row : matrix){
            auto it = lower_bound(row.begin(),row.end(),target);
            if(it != row.end() && *it == target){
                return true;
            }
        }
        return false;
    }
};

 

相关文章