BM18. [二维数组中的查找]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM18. 二维数组中的查找

https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=295&sfm=github&channel=nowcoder

题目的主要信息：

• 矩阵的行元素和列元素都是有序的，从左到右递增，从上到下递增，完全递增元素不会有重复
• 找到矩阵中有没有给定元素即可

方法一：暴力法
具体做法：

从上到下每行，每行中从左至右遍历二维数组，依次查找。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  //优先判断特殊
            return false;
        int n = array.size();
        if(array[0].size() == 0)  
            return false;
        int m = array[0].size();
        for(int i = 0; i < n; i++)  //两层循环，遍历二维数组
            for(int j = 0; j < m; j++)
                if(array[i][j] == target)  //找到target
                    return true;
        return false;
    }
};

复杂度分析：

• 时间复杂度：，二维数组的遍历
• 空间复杂度：，没有使用额外空间

方法二：二分查找

具体做法：

既然矩阵里面的元素是有序且无重复的，我们可以好好利用一下。

首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：
左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。
我们可以在查找时使用二分法：
首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        if(array.size() == 0)  //优先判断特殊
            return false;
        int n = array.size();
        if(array[0].size() == 0)  
            return false;
        int m = array[0].size();
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //从最左下角的元素开始往左或往上
            if(array[i][j] > target)   //元素较大，往上走
                i--;
            else if(array[i][j] < target) //元素较小，往右走
                j++;
            else
                return true;
        }
        return false;
    }
};

复杂度分析：

• 时间复杂度：，最多经过一行一列
• 空间复杂度：，没有使用额外空间