nc86.矩阵元素查找

1. 思路一: (笨办法, 暴力搜索, 不合要求)

直接遍历二维数组即可.

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        vector<int> res(2);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (mat[i][j] == x) {
                    res[0] = i, res[1] = j;
                    return res;
                }
            }
        }

        return res;
    }
};
  • 时间复杂度: O(nm). 因为遍历了一遍整个矩阵
  • 空间复杂度: O(1). 没有使用数组作为额外空间.

2. 思路二: 从左下往右上找(贪心)

思路一是最笨的暴力办法, 我们没有使用一个条件, 就是该矩阵的每行、每列都是从小到大递增的. 根据这个条件, 我们可以从左下找, 然后这样判断:

  • 如果当前位置的数大于目标值: 那么根据该矩阵的特性, 其右边的数只可能更大, 我们往上走一步.
  • 如果当前位置的数小于目标值: 那么上边的数只可能更小, 我们往右走.

样例

例如，我们从左下角5开始，寻找目标为7. 算法流程如下：

  • 5<7, 说明5上边的一定不是解(比5更小)，去掉最左边一列，向右走
  • 9>7，说明9右边的一定比9更大，向上走
  • 8>7， 8右边的一定比9更大，向上走
  • 5<7, 5上边的一定比5更小， 向右走
  • 7==7， 找到答案

根据贪心性质, 我们是从左下开始寻找的, 搜索路径只会单调的向右上, 不会往左、往下走, 所以肯定能找到答案. 

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        vector<int> res(2);

        int i = n-1, j = 0; //左下角

        // 不走到外面
        while (i >= 0 && j <= m-1) {
            if (mat[i][j] > x) i--; //往上走
            else if (mat[i][j] < x) j++; // 往右走
            else {
                // 找到了
                res[0] = i, res[1] = j;
                return res;
            }
        }

        // 走到边上也没找到, 无解
        return res;
    }
};
  • 时间复杂度: O(n+m). 因为遍历过程中, 只是往上和右走, 最坏的情况走n+m步走到边上, 所以最慢的复杂度是n+m.
  • 空间复杂度: O(1). 没有使用数组作为额外空间.

3. 思路三: 二分搜索

因为每一行都是递增的, 且我们不知道答案在哪一行, 所以可以暴力枚举每一行, 再逐行对列二分搜索x.

class Solution {
public:
    vector<int> findElement(vector<vector<int> > mat, int n, int m, int x) {
        vector<int> res(2);

        // 枚举i行
        for (int i = 0; i < n; i++) {
            // 如果第i行最左边都比x大,或者最右边都比x小, 那么答案肯定不在这一行
            if (mat[i][0] > x || mat[i][m-1] < x) continue;

            int l = 0, r = m-1; // 二分查找左右端点
            while (l <= r) {
                int mid = (l+r) >> 1;
                // 如果中点元素大于x, 答案在左边
                if (mat[i][mid] > x) r = mid-1;
                // 小于x, 答案在右边
                else if (mat[i][mid] < x) l = mid+1;
                // 找到了
                else {
                    res[0] = i, res[1] = mid;
                    return res;
                }
            }
        }
        return res;
    }
};
  • 时间复杂度: O(nlogm). 遍历过程中, 每一行都对长度为m的数组二分搜索了一次.
  • 空间复杂度: O(1). 没有使用数组作为额外空间.