4.二维数组中的查找.md

4.二维数组中的查找

题目描述

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

例子

输入一个数组：

num[ 3 ][ 4 ] = [  
1 , 4 , 6 , 28 ,  
2 , 7 , 32 , 30 ,  
10 , 11 , 67 , 79  
]

需要查找一个数字 32 ，则返回 true。

思路 & 解答

暴力破解

直接暴力遍历，但是在最坏的情况是遍历完所有的元素才能获取结果。如果这个数组规模是 n * m，那么时间复杂度就是 O(n × m)，没有借助其他的空间，空间复杂度为 O(1)。

比较查找法

但是我们换一种思路，我们选定左下角的 10 ( num[2][0], i = 2, j = 0 )作为起点，如果大于 10 ,那么 i + 1 ,如果小于 10 ，则 j + 1 ，则下一个查找的数字是 11 ,我们知道 32 仍然比 11 大，则往右找到 67 ，继而 32 比 67 小，我们应该往上找，找到了 32 。
如果找 28 ，则是最坏的结果，查找知道数组的右上角结束，这样一来，最坏的结果就是 O（n + m）。

Java 实现代码如下：

public class Solution {
    public boolean Find(int target, int[][] array) {
        int size = array.length;
        int length = array[0].length;
        int i, j;
        for (i = size - 1, j = 0; i >= 0 && i < size && j >= 0 && j < length; ) {
            if (array[i][j] == target) {
                return true;
            }
            if (array[i][j] < target) {
                j++;
                continue;
            }
            if (array[i][j] > target) {
                i--;
                continue;
            }
        }
        return false;
    }
}

C++ 代码如下：

#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    bool Find(int target, vector<vector<int>> array) {
        int size = array.size();
        int length = array[0].size();
        int i, j;
        for (i = size - 1, j = 0; i >= 0 && i < size && j >= 0 && j < length;) {
            if (array[i][j] == target) {
                return true;
            }
            if (array[i][j] < target) {
                j++;
                continue;
            }
            if (array[i][j] > target) {
                i--;
                continue;
            }
        }
        return false;
    }
};

int main() {
    vector<vector<int>> array = {{1, 2, 8,  9},
                                 {2, 4, 9,  12},
                                 {4, 7, 10, 13},
                                 {6, 8, 11, 15}};
    Solution solution = Solution();
    cout << solution.Find(7, array) << endl;
    cout << solution.Find(3, array) << endl;
    return 0;
}