BM18. [二维数组中的查找]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM18. 二维数组中的查找
题目的主要信息：
- 矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复
- 找到矩阵中有没有给定元素即可
方法一：暴力法
具体做法：
从上到下每行，每行中从左至右遍历二维数组，依次查找。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if(array.size() == 0) //优先判断特殊
return false;
int n = array.size();
if(array[0].size() == 0)
return false;
int m = array[0].size();
for(int i = 0; i < n; i++) //两层循环，遍历二维数组
for(int j = 0; j < m; j++)
if(array[i][j] == target) //找到target
return true;
return false;
}
};
复杂度分析：
- 时间复杂度：
，二维数组的遍历
- 空间复杂度：
，没有使用额外空间
方法二：二分查找
具体做法：
既然矩阵里面的元素是有序且无重复的，我们可以好好利用一下。
首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：
左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。
我们可以在查找时使用二分法：
首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
class Solution {
public:
bool Find(int target, vector<vector<int> > array) {
if(array.size() == 0) //优先判断特殊
return false;
int n = array.size();
if(array[0].size() == 0)
return false;
int m = array[0].size();
for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //从最左下角的元素开始往左或往上
if(array[i][j] > target) //元素较大，往上走
i--;
else if(array[i][j] < target) //元素较小，往右走
j++;
else
return true;
}
return false;
}
};
复杂度分析：
- 时间复杂度：
，最多经过一行一列
- 空间复杂度：
