题解 | #二维数组中的查找#
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
1. 解题思路
一维数组查找使用二分法的思路是是中间元素 mid 先和 target 比较,相等直接返回 true,否则:
若mid < target, 在右半区间继续查找;
若 mid > target, 在左半区间继续查找。
同理,二维数组可以将左下角元素或右上角元素作为中间元素,以右上角元素作为 mid 举例。mid先和target比较:
相等直接返回 true;
若mid < target, 因为同一行左侧元素都比mid小,所以将同列下一行元素作为新的mid;
若mid > target, 因为同一列下侧元素都比mid大,所以将同行左一列元素作为新的mid。
循环比较mid 和 target 是否相等,在极端情况下mid一直下移到>行数,或一直左移<0。因此边界条件设为"while(i<row && j>-1)",循环结束后没找到target,说明target不在数组中,返回false。
2. 代码实现
class Solution { public: bool Find(int target, vector<vector<int>> array) { int row,col,i,j; row = array.size(); i = 0; j = array[0].size()-1; while(i<row && j>-1){ if(array[i][j]==target) return true; else if(array[i][j]>target) j--; else i++; } return false; } };
3. 复杂度分析
时间复杂度:最坏情况下,mid从初始位置到达对角位置,进入循环次数最大为 行数+列数,故为O(m+n)。
空间复杂度:定义变量数目与问题规模无关,故为O(1)。