题目

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

考察点和难度

• 考察知识点：数组
• 难度：4星（共5星）

分析

最简单的求解方式是遍历整个二维数组，可以查询到是否有目标值，但是时间复杂度为O(rows * cols)，面试官是不会满意的。

为了降低时间复杂度，需要运用该二维数组的特性，即横向和纵向的递增特性。

该二维数组中的任意一个点P，其左前区域都小于点P的值，其右后区域都大于点P的值，因此可以利用该特性在查询时缩小查询范围。

从最右上角的点P出发，如果点P的值等于目标值，则直接输出true；如果点P的值大于目标值，可以往左查找第一个小于等于目标值的点PL，此时点PL成为新的“右上角”，且点PL的右后部分区域的数值由于肯定大于目标值，因此可以被剔除出查询范围；如果点P的值小于目标值，可以往下查询第一个大于等于目标值的点PD，此时点PD成为新的“右上角”，且点PD的左前部分区域的数值由于肯定小于目标值，因此也可以被剔除出查询范围。得到新的“右上角”之后，重复该操作，就能遍历整个二维数组来查询目标值，且由于只在横向和纵向往左下角移动，剔除了无需查询的区域范围，因此时间复杂度为O(rows + cols)。

为什么从右上角出发开始查询？对于右上角的点P来说，其左边的数值都小于点P的值，其下面的数值都大于点P的数值，当给定目标值之后，如果目标值小于点P的数值，那么点P所在列就可以被剔除；如果目标值大于点P的数值，那么点P所在行就可以被剔除，这样就缩小了查询范围。

从左下角出发，往右上角查询也是可以的。

代码实现（java）

    public boolean hasNumInArray(int[][] array, int rows, int cols, int num) {
        // 检查输入参数
        if (array == null) {
            throw new NullPointerException();
        }
        if (rows < 1 || cols < 1) {
            throw new IllegalArgumentException();
        }
        int rowSize = array.length;
        if (rowSize != rows) {
            throw new IllegalArgumentException();
        }
        int colSize = array[0].length;
        if (colSize != cols) {
            throw new IllegalArgumentException();
        }

        // 从右上角数字开始，往左下角找目标数字，理论上时间复杂度为O(rows+cols)
        int i = 0, j = cols - 1;
        while ((i <= (rows - 1)) && (j >= 0)) {
            // 判断当前右上角的值是否为目标值
            if (array[i][j] == num) {
                return true;
            } else if (array[i][j] > num) {
                // 当前右上角的值比目标值大，则往左找新的“右上角”，且新的“右上角”的右后部分区域由于肯定大于目标值，因此可被剔除
                while ((j >= 0) && (array[i][j] > num)) {
                    j = j - 1;
                }
            } else {
                // 当前右上角的值比目标值小，则往下找新的“右上角”，且新的“右上角”的左前部分区域由于肯定小于目标值，因此可被剔除
                while ((i <= (rows - 1) && (array[i][j]) < num)) {
                    i = i + 1;
                }
            }
        }
        return false;
    }