剑指offer(3) 二维数组中的查找

1.题目

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

2.解题分析

查找整数时，如果从左上角开始查找，情况较为复杂，可以转换思路，从右上角开始查找：左边数字比较小，右边数字比较大，容易进行判断。

例如：给出如下数组

1 2 8 9

2 4 9 12

4 7 10 13

6 8 11 15

如果查找7返回true

查找5返回false

3.代码

/*
 * 判断二维数组matrix中是否含有整数a
 * 返回值为a的下标，{-1，-1}代表不存在
 */
public int[] find(int[][] matrix, int a) {
    int[] index = { -1, -1 };
 
    // 判断数组是否正确
    if (matrix == null || matrix.length <= 0) {
        System.out.println("数组无效！");
        return index;
    }
    // 判断数组数字的大小是否符合大小规则
    int columns = matrix[0].length;
    for (int i = 0; i < matrix.length; i++) {
        if (matrix[i].length != columns) {
            System.out.println("数组列数不一致！");
            return index;
        }
        for (int j = 0; j < matrix[i].length; j++) {
            if (i == 0 && j == 0)
                // matrix[0][0]不比较
                break;
            if (i == 0) { // 第一行的数，仅和前一列的数比较
                if (matrix[i][j] < matrix[i][j - 1]) {
                    System.out.println("数组中数字大小不符合要求！");
                    return index;
                }
            } else if (j == 0) { // 第一列的数，仅和前一行的数比较
                if (matrix[i][j] < matrix[i - 1][j]) {
                    System.out.println("数组中数字大小不符合要求！");
                    return index;
                }
            } else if (matrix[i][j] < matrix[i - 1][j] || matrix[i][j] < matrix[i][j - 1]) {
                // 其余位置的数字，和前一行或前一列的比较
                System.out.println("数组中数字大小不符合要求！");
                return index;
            }
        }
    }
 
    // 正式查找
    int row = 0; // 行数
    int column = matrix[0].length - 1; // 列数
    while (row <= matrix.length - 1 && column >= 0) {
        if (a == matrix[row][column]) {
            index[0] = row;
            index[1] = column;
            System.out.println("数字" + a + "在二维数组中的下标为：" + index[0] + "," + index[1]); // 注意下标是从0开始的
            return index;
        } else if (a < matrix[row][column]) {
            column--;
        } else {
            row++;
        }
    }
    System.out.println("数组中不含数字：" + a);
    return index;
}