抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

二维数组的查找

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

例如下面的二维数组就是每行、每列都递增排序。如果在这个数组中查找数字7, 则返回true; 如果查找数字5, 由于数组不含有该数字,则返 回false。

{ 1, 2, 8, 9 }
{ 2, 4, 9, 12 }
{ 4, 7, 10, 13 }
{ 6, 8, 11, 15 }

解题思路:当我们需要解决一个复杂的问题时,一个很有效的办法就是从一个具体的问题入手,通过分析简单具体的例子,试图寻找普遍的规律。针对这 个间题,我们不妨也从一个具体的例子入手。下面我们以在题目中给出的 数组中查找数字7为例来一步步分析查找的过程。

具体思路:从数组的一个角上选取数字来和要查找的数字做比较

首先我们选取数组右上角的数字9。由于9大于7,并且9还是第4列的第一个(也是最小的)数字,因此7不可能出现在数字9所在的列。于是我们把这一列从需要考虑的区域内剔除,之后只需要分析剩下的3列。第3列的8情况与第四列的9相同,所以可以剔除,第二列的2比我们要找的7小,这时我们就需要将行+1,以此类推,当刚好处于7时,结果便出来了。

解法一:按例题中的从右上角开始

public static boolean findNumFromRight(int[][] matrix, int rows, int clomuns, int num) {
    if (matrix == null || rows < 0 || clomuns < 0) {
        return false;
    }
    // 从右上角开始 如果右上角的比要找的数大 则列-- 反之 则行++
    int row = 0;
    int clomun = clomuns - 1;
    boolean isFound = false;
    while (row < rows && clomun >= 0) {

        if (matrix[row][clomun] == num) {
            isFound = true;
            break;
        }
        if (matrix[row][clomun] > num) {
            // 右上角第一个大于我们要找的
            --clomun;
        } else {
            ++row;
        }

    }
    return isFound;
}

解法二:选取左下角的数字

public static boolean findNumFromLeft(int[][] matrix, int rows, int clomuns, int num) {
    if (matrix == null || rows < 0 || clomuns < 0) {
        return false;
    }
    // 从左下角开始 如果左下角的比要找的数大 则行-- 反之 则列++
    int row = rows - 1;
    int clomun = 0;
    boolean isFound = false;
    while (clomun < clomuns && row >= 0) {

        if (matrix[row][clomun] == num) {
            isFound = true;
            break;
        }
        if (matrix[row][clomun] > num) {
            // 左下角第一个大于我们要找的
            --row;
        } else {
            ++clomun;
        }

    }
    return isFound;
}

需要注意的是,我们不能选择左上角或者右下角,因为这样就不符合我们找出来的规律了。

测试main方法:

public static void main(String[] args) {
    int[][] matrix = {
            { 1, 2, 8,  9  },
            { 2, 4, 9,  12 },
            { 4, 7, 10, 13 },
            { 6, 8, 11, 15 }
    };

    System.out.println("row:" + matrix.length + " column:" + matrix[0].length);
    boolean isRightFound = findNumFromRight(matrix, matrix.length, matrix[0].length, 7);
    System.out.println("findNumFromRight " + isRightFound);

    boolean isLeftFound = findNumFromLeft(matrix, matrix.length, matrix[0].length, 7);
    System.out.println("findNumFromLeft " + isLeftFound);
}

这题看上去复杂,但是如果发现了规律,则很简单了。

总结上述查找的过程:

首先选取数组中右上角的 数字。 如果该数字等于要查找的数字, 查找过程结束;如果该数字大于要 查找的数字, 剔除这个数字所在的列:如果该数字小于要查找的数字, 剔除这个数字所在的行。

也就是说如果要查找的数字不在数组的右上角, 则每一次都在数组的查找范围中剔除一行或者一列, 这样每一步都可以缩小 查找的范围, 直到找到要查找的数字, 或者查找范围为空。


0条评论

发表评论