Leetcode 74 Search in a 2D array

题意： 二维矩阵中搜索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 row
        int 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;
    }
};

原文地址：https://blog.csdn.net/xxxmmc/article/details/143624335

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！