剑指Offer04二维数组中的查找

2023-07-29 78

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 剑指Offer04二维数组中的查找

🔎概述

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

🔎题解

🌻解法1(朴素解法)

public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int[] ints : matrix) {
            for (int x : ints) {
                if(x == target)
                    return true;
            }
        }
        return false;
 }

对于以上矩阵,我们只需要逐个遍历,就可以判断出该矩阵是否包含目标值target

🌻解法2(二分查找)

public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        int n = matrix.length;
        //逐层遍历,看该层是否包含target
        //最后如果都未包含,返回false
        for (int i = 0; i < n; i++) {
            if(findTarget(matrix[i],target))
                return true;
        }
        return false;
}
//二分查找
private static boolean findTarget(int[] arr,int target) {
        int n = arr.length;
        if(n == 0) return false;
        int left = 0,right = n - 1;
        while(left <= right) {
            int mid = left + ((right - left) >> 1);
            if(arr[mid] < target) {
                left = mid + 1;
            }else if(arr[mid] > target){
                right = mid - 1;
            }else {
                return true;
            }
        }
        return false;
}

解法2是分别遍历二维数组的每一层,然后利用二分法去判断该层是否包含目标值target

如果包含,返回true

遍历结束,未包含target,返回false

对于解法1与解法2,我们比较容易想到,下面来介绍另一种更高效的解法

🌻解法3(Z字形查找)

public static boolean findNumberIn2DArray3(int[][] matrix, int target) {//解法3
        if(matrix == null || matrix.length == 0) return false;
        int n = matrix.length,m = matrix[0].length;
        //n-->二维数组行数,m-->每一行的元素个数
        int index1 = 0,index2 = m - 1;
        while(index1 < n && index2 >= 0) {
            if(matrix[index1][index2] < target) {
                index1++;
            }else if(matrix[index1][index2] > target) {
                index2--;
            }else {//matrix[index1][index2] == target
                return true;
            }
        }
        return false;
}