题解 | #二维数组中的查找#

NC29 矩阵查找

题意分析：

实现一个对有序矩阵查找函数

题解一（暴力查找）：

对矩阵的每一行进行查找，由于矩阵的每一行都是有序的，因此我们可以对每一行进行二分查找。

代码实现如下

bool searchMatrix(vector<vector<int> >& matrix, int target) {
        for(int i=0;i<matrix.size();i++){
           if( binary_search(matrix[i].begin(), matrix[i].end(), target)){
               return true;
           }
        }
        return false;
    }

时间复杂度： $O(nlg \ n)$ ，我们对矩阵的n行进行了二分查找，二分查找时间复杂度 $O(lg n)$ ，总的时间复杂度 $O(nlg\ n)$ 。

空间复杂度： $O(n)$ 。没有申请额外的空间。

题解二（杨氏矩阵查找）：

题目所提供的矩阵，是一种特殊的矩阵，称作杨氏矩阵，其有特定的查找算法，时间复杂度 $O(n+m)$ m,n分别为矩阵的两个维度。查找算法步骤如下：

从矩阵的左下角或者矩阵的右上角处开始递归运行，以左下角为例，value为要查找的值，(i,j)为当前矩阵中的位置，初始为(M-1, 0)。
如果超过了矩阵范围则说明不存在这样的元素，返回false。
否则的话，如果当前位置的值大于value，说明要移动位置(向上移一行)，使得数值减小，即递归使得i=i-1；如果当前位置的值小于value，说明要移动位置(向右移一列)，使得数值增大，即递归使得j=j+1；如果刚好等于value，返回当前的位置true即可。
举个例子：

查找过程如红色箭头所示：
1 .我们在6的位置，发现6比12小，那么6上面的数比6小，右边的数比6大，那么只能向右边走
同理在8，11，一样
当移动到了15，15比12大，那么12一定在15的上方，向上移动
同理在13一样，最后在12处找到了目标值。

下面给出其代码实现

bool searchMatrix(vector<vector<int> > &matrix, int target) {
    int m = matrix.size(), n = matrix[0].size();
    int i = m - 1, j = 0;
    while (i >= 0 && j <= n - 1) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] < target) {
            //如果目标值大于当前位置的值，当前位置右移
            j++;
        } else {
            //如果目标值小于当前位置的值，当前位置上移
            i--;
        }
    }
    return false;
}

时间复杂度： $O(m+n)$ 。

空间复杂度： $O(1)$ ，没有申请额外的空间。