关于java:牛客网高频算法题系列BM18二维数组中的查找

31次阅读

共计 1358 个字符,预计需要花费 4 分钟才能阅读完成。

牛客网高频算法题系列 -BM18- 二维数组中的查找

题目形容

在一个二维数组 array 中(每个一维数组的长度雷同),每一行都依照从左到右递增的程序排序,每一列都依照从上到下递增的程序排序。请实现一个函数,输出这样的一个二维数组和一个整数,判断数组中是否含有该整数。

原题目见:二维数组中的查找

解法一:二分查找法

因为原二维数组是严格有序的,即从左到右递增、从上到下递增,所以能够采纳二分查找的形式进行解决。具体处理过程如下:

  • 首先解决非凡场景,当数组为空时,不可能找到目标值,间接返回 false。
  • 否则,从二维数组的右上角的地位开始,作为二分的中点,x、y 别离为二维数组的坐标地位,而后循环解决直到找到目标值:

    • 查找终结的条件就是 x、y 其中一个走到了二维数组的边界之外;
    • 如果以后地位的值和目标值雷同,阐明找到了目标值,返回 true;
    • 如果以后地位的值比目标值大,则往左挪动,因为右边的数更小,而后进行下一轮查找;
    • 如果以后地位的值比目标值小,则往下挪动,因为下边的数更大,而后进行下一轮查找。
  • 最初,如果查找实现没有找到目标值,则返回 false。

代码

public class Bm018 {

    /**
     * 二分查找法
     *
     * @param target 目标值
     * @param array  二维数组
     * @return
     */
    public static boolean find(int target, int[][] array) {
        // 首先解决非凡场景,当数组为空时,不可能找到目标值,间接返回 false
        if (array == null || array.length == 0 || array[0].length == 0) {return false;}
        // 而后从二维数组的右上角的地位开始,作为二分的中点,x、y 别离为二维数组的坐标地位
        int x = 0, y = array[0].length - 1;
        // 查找终结的条件就是 x、y 其中一个走到了二维数组的边界之外
        while (x < array.length && y >= 0) {if (array[x][y] == target) {
                // 如果以后地位的值和目标值雷同,阐明找到了目标值,返回 true
                return true;
            } else if (array[x][y] > target) {
                // 如果以后地位的值比目标值大,则往左挪动,因为右边的数更小,而后进行下一轮查找
                y--;
            } else if (array[x][y] < target) {
                // 如果以后地位的值比目标值小,则往下挪动,因为下边的数更大,而后进行下一轮查找
                x++;
            }
        }
        // 如果查找实现没有找到目标值,则返回 false
        return false;
    }

    public static void main(String[] args) {int[][] array = {{1, 2, 8, 9}, {2, 4, 9, 12}, {4, 7, 10, 13}, {6, 8, 11, 15}};
        // 测试用例一:冀望输入:true
        int target1 = 7;
        System.out.println(find(target1, array));

        // 测试用例二:冀望输入:false
        int target2 = 3;
        System.out.println(find(target2, array));
    }
}

$1.01^{365} ≈ 37.7834343329$
$0.99^{365} ≈ 0.02551796445$
置信保持的力量!

正文完
 0