剑指offer——面试题4：二维数组中的查找

1.题目描述：

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下的顺序排序。请完成一个函数，判断数组中是否包含指定的数字。

2.解题思路：

可以选择数组左下角的数字进行比较，因为如果要找的数字num比它小，则说明需要去它上边的一行去判断；如果要找的数字num比它大，则说明需要去它右边的一列去判断。事实上，也可以选择右上角的数字开始，但是不能选择左上角或者右下角，因为要保证所选数字的两条边一条在递增一条在递减，否则就不知道比较后该往哪里继续判断。

3.代码实现：

public class Offer_4 {
    public static void main(String[] args) {
        int[][] array = {
                {1, 2, 8, 9},
                {2, 4, 9, 2},
                {4, 7, 10, 13},
                {6, 8, 11, 15}
        };
        System.out.println(FindNum(array, 12));
    }

    private static boolean FindNum(int[][] array, int num) {
        if (array == null) {
            return false;
        }
        int x = array.length - 1;
        int y = 0;

        while (x >= 0 && y < array.length) {
            if (num > array[x][y]) {
                y++;
            } else if (num < array[x][y]) {
                x--;
            } else {
                return true;
            }
        }
        return false;
    }
}

复杂度分析：

• 时间复杂度：O(n)，对于大小为n x n的数组，最少时间是第一次就找到num；最大时间是num在所选的数字的对角位置，需要判断2n -1次，总的时间复杂度为O(n).
• 空间复杂度：O(1)，不需要额外开辟新的空间。