题解 | #二维数组中的查找#
二维数组中的查找
https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param target int整型 * @param array int整型vector<vector<>> * @return bool布尔型 */ bool Find(int target, vector<vector<int> >& array) { // write code here // for(int i=0;i<array.size();++i){ // for(int j=0;j<array[0].size();++j){ // if(target==array[i][j]){ // return true; // } // } // } // return false; //数组在C++中存放地址连续,在牛客上操作了一下不连续 // int *p; // p=&array[0][0]; // for(int i=0;i<array.size()*array[0].size();++i){ // cout<<*p<<endl; // if(target==*p){ // return true; // } // p+=1; // } // return false; // } //二分查找把每一行看成一个递增的数组时间复杂度O(nlogn) for(int i=0;i<array.size();++i){ int low=0; int high=array[0].size()-1; while(low<=high){ int mid=(low+high)/2; if(array[i][mid]>target){ high=mid-1; }else if(array[i][mid]<target){ low=mid+1; }else{ return true; } } } return false; } };
每一行用二分法O(nlogn)