二维数组中的查找

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

二维数组中的查找

2023-02-14 13:57:56 来源：博客园

(资料图)

问题：矩阵从左至右、从上至下非递减顺序，查找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>& 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>& 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;    }};

关键词：时间复杂度从上至下空间复杂度