剑指 Offer 04. 二维数组中的查找

原题链接：剑指 Offer 04. 二维数组中的查找

 

solution:

        暴力模拟，时间复杂度O(m * n)

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(auto &x : matrix)
            for(auto &y : x) {
                if(y == target) return true;
            }
        return false;
    }
};

        逐行进行二分查找时间复杂度O(nlogn)

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        int n = matrix.size();
        if (matrix.size() == 0 || matrix[0].size() == 0)
            return false;
        for(int i = 0;i < n;i++) {
            if(binSearch(matrix[i], target)) return true;
        }
        return false;
    }

    bool binSearch(vector<int> &nums, int target) {
        int l = 0,r = nums.size() - 1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if(nums[l] == target) return true;
        return false;
    }
};

从右上角开始查找,如果matrix[x][y] > target,y++,else x--

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return false;
        int n = matrix.size(),m = matrix[0].size();
        int x = n - 1,y = 0;
        while(x >= 0 && y < m) {
            if(matrix[x][y] == target) return true;
            if(matrix[x][y] < target) y++;
            else x--;
        }                
        return false;
    }
};