文章首发于:https://blog.csdn.net/donaldsy/article/details/106355996
1、暴力法
直接遍历进行查找,试一试的心态,原以为会超时,没想到通过了。
bool Find(int target, vector<vector<int> > array) { for(int row = 0; row < array.size();++ row) { for(int col = 0; col < array[row].size(); ++col) { if(target == array[row][col]) return true; } } return false; }
第一次提交:运行时间:10ms,占用内存:1492k
第二次提交:运行时间:13ms,占用内存:1372k
2、剑指offer书中思路
先从右上角开始进行比较,比较情况会有如下三种结果:
- target == array[i][j],刚好相等,直接返回
- target < array[i][j],target更小,说明不在该列,删除该列元素。
- target > array[i][j],target更大,说明不在该行,删除该行元素。
完整代码为:
bool Find(int target, vector<vector<int> > array) { int row = 0; int col = array[0].size()-1; //这里需要注意 while(row < array.size() && col >= 0) { if(target == array[row][col]) { return true; } else if(target < array[row][col]) { -- col; }else { ++ row; } } return false; }
第一次提交:运行时间:17ms,占用内存:1480k
第二次提交:运行时间:13ms,占用内存:1484k
根据提交结果,没想到前面的方法更快😂