剑指offer刷题记—第4题_二维数组中的查找

约定不等于承诺〃 2021-09-23 09:50 237阅读 0赞

**
     * @program: suanfa
     * @description: 二维数组中查找，给定一个二维数组，其每一行从左到右递增排序，
     * 从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中
     * @author: zi jian
     * @create: 2019-10-23 16:37
     */
    public class FindNumber_4 {
        //思路是确定一个数如果正常查询的话会发现向右向下都是在递增，
        // 所以我们可以换个思路就是让其一个方向递增一个方向递减则可以锁定数字
        public static boolean findNumeber(int[][] nums, int m) {
            if (nums.length == 0 || nums[0].length == 0) {
                return false;
            }
            //判断是否会重复
            boolean[][] judge = new boolean[nums.length][nums[0].length];
            int x = nums.length - 1;
            int y = 0;
            //循环找出合适的位置
            while (x >= 0 && y < nums[0].length) {
                if (nums[x][y] == m) {
                    System.out.println("X = " + x + " Y = " + y);
                    return true;
                } else if (m > nums[x][y]) {
                    y++;
    
                } else {
                    x--;
                }
                //进入防止进入死循环比对过的点不必再比如果再比说明没有合适的位置
                if(x >= 0 && y < nums[0].length){
                    if (!judge[x][y]) {
                        judge[x][y] = true;
                    } else {
                        return false;
                    }
                }
    
            }
            return false;
        }
    
        public static void main(String[] args) {
            int[][] nums = {
                    {1, 4, 7, 11, 15},
                    {2, 5, 8, 12, 19},
                    {3, 6, 9, 16, 22},
                    {10, 13, 14, 17, 24},
                    {18, 21, 23, 26, 30}
            };
    
            findNumeber(nums,9);
        }
    }