剑指Offer之二维数组中查找目标数

题目描述

​ 在一个二维数组中（每个一维数组的长度相等），每一行都是从左到右递增的顺序排序，每一列都是从上到下递增的顺序排序，输入这样一个二维数组和一个整数，判断该整数是否在二维数组中。

解题思路及代码

// 暴力查找法，通过遍历整个二维数组进行判断

    public static boolean violence(int[][] arr,int target) {

        for (int i = 0; i < arr.length; i++) {

            for (int j = 0; j < arr[0].length; j++){

                if (arr[i][j] == target)

                    return true;

            }

        }

        return false;

    }

    /**

     *   tips: 二维数组其实就是元素类型为数组的一维数组。 ex:  {{1，2，3}，{2，3，4}，{3，4，5}}

     *  可理解为： 1，2，3

     *            2，3，4

     *            3，4，5

     *  此时我们可以将target 和每一行的最后一个元素作比较，有三种情况发生

     *  1. 相等   则直接返回true 即二维数组中存在该元素

     *  2. 最后一个元素 > target   则target不可能存在当前行中，直接跳转到下一行

     *  3. 最后一个元素 < target   则每个一维数组的最后一行都不用比较了

     *

     */

    public static boolean find(int[][] array,int target) {

        int maxX = array.length;

        int maxY = array[0].length;

        int x = 0;

        int y = maxY - 1;

        while (x < maxX && y >= 0) {

            if (array[x][y] == target)

                return true;

            if (array[x][y] > target)

                y--;

            else

                x++;

        }

        return false;

    }