服装网站建设比较好_域名是什么样子_网站建设技术托管_互联网营销师证书骗局

题意： 二维矩阵中搜索target
https://leetcode.com/problems/search-a-2d-matrix/description/

解法：把二维矩阵展开后得到从小到大的排列，然后去搜索target是否在这个排列中中存在，如果存在那就返回。

//最优解class Solution {
public:bool searchMatrix(vector<vector<int>>& a, int t) {int m = a.size();int n = a[0].size();int l = 0;int r = m * n - 1;while (l < r) {int mid = l + (r - l) + 1 / 2;int x = mid / n; int y = mid % n;if (a[x][y] <= t) {l = mid;} else {r = mid - 1;}}return a[l/n][l%n] == t;}
};

算法复杂度：O(mnlogmn), m 为数组的长，n为宽
空间复杂度：O(1)

复杂的解法，两遍二分

class Solution {
public:bool searchMatrix(vector<vector<int>>& a, int t) {// find the rowint l = 0;int r = a.size() - 1;while ( l < r) {int mid = l + (r - l) + 1/ 2;if(a[mid][0] <= t) {l = mid;} else {r = mid - 1;}}if (a[l][0] > t) {return false;}int row = l;l = 0;r = a[0].size() - 1;while (l < r) {int mid = l + (r-l) + 1/ 2;if (a[row][mid] <= t) {l = mid;} else {r = mid - 1;}}return a[row][l] == t ? true : false;}
};