剑指4：二维数组中的查找

传送门

nowcoder
leetcode

题目描述

在一个二维数组中（每个一维数组的长度相同），
每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

C++ 代码 - nowcoder

/*
    从右上向左下走。变大向下走，r++ ; 变小向左走，c--
    从左下向右上，也可以。

    时间复杂度：O(n)
*/
bool Find(int target, vector<vector<int> > array) {
    if (array.size() == 0 || array[0].size() == 0) return false;

    int rows = array.size(), cols = array[0].size();
    int r = 0, c = cols - 1;
    // 变大向下走，r++ ; 变小向左走，c--
    while (r < rows && c >= 0) {
    	if (array[r][c] > target) c --;
    	else if (array[r][c] < target) r ++;
    	else return true;
    }
    return false;
}

/*
    每一行的数组用二分法查找

    时间复杂度：O(nlogn)
*/
class Solution {
public:
    bool Find(int target, vector<vector<int> >& array) {
        if (array.size() == 0 || array[0].size() == 0) return false;

        int rows = array.size(), cols = array[0].size();
        for (int i = 0; i < rows; i ++) {
            int l = 0, r = cols - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (array[i][mid] <= target) l = mid;
                else r = mid - 1;
            }
            if (array[i][r] == target) return true;
        }
        return false;
    }
};

C++ 代码 - leetcode

/*
    从右上向左下走，从左下向右上也可以。
    变大向下走，r++; 变小向左走，c--

    时间复杂度：O(n)
*/
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;

        int rows = matrix.size(), cols = matrix[0].size();
        int i = 0, j = cols - 1;
        while (i < rows && j >= 0) {
            if (matrix[i][j] > target) j --;
            else if (matrix[i][j] < target) i ++;
            else return true;
        }
        return false;
    }
};

/*
    每一行的数组用二分法查找

    时间复杂度：O(nlogn)
*/
class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return false;

        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; i ++) {
            int l = 0, r = n - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (matrix[i][mid] <= target) l = mid;
                else r = mid - 1;
            }
            if (matrix[i][r] == target) return true;
        }
        return false;
    }
};