【算法怎么就这么难——挑战剑指offer】系列01:二维数组的查找

本系列的算法原题来自于“牛客网-剑指offer”,写这个板块,不仅仅是解决算法问题本身,更是手动提高难度、自行变式,思考更多的解决方案,以带给自己一些启发。

1. 【二维数组的查找】原始题目

算法原题链接:https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

原题目描述:

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

比方说下面的一个数组:

最简单的设计

直接遍历数组即可。该算法的时间复杂度:O(n2)

public static boolean find(int target, int[][] array) {
    for (int[] arr : array) {
        for (int num : arr) {
            if (num == target) {
                return true;
            }
        }
    }
    return false;
}

但这样肯定不是最好的办法,我们要想:如何充分运用数组的规律和特性,把时间复杂度降低呢?

降低时间复杂度

因为每一行、每一列都是由小到大排列,所以可以选择从左下角/右上角出发,采用比对值、移动坐标的方法查找。

public static boolean find(int target, int[][] array) {
    //从右上角开始
    int x = 0, y = array[0].length - 1;
    while (array[x][y] != target) {
        if (array[x][y] > target) {
            y--;
        }else {
            x++;
        }
        //每移动一次,就要校验指针坐标是否已越出数组边界
        if (x >= array.length || y < 0) {
            return false;
        }
    }
    //只要出了循环,代表找到了
    return true;
}

按道理已经到此为止了是吧,但是我们讲:程序好或者坏,要看三个方面:正确性、可读性、健壮性。现在的算法中,正确性和可读性都实现了,但是会出现一些问题:

----| 如果传入空数组,或者二维数组中的每一个子数组都是空,会抛NullPointerException!

提高程序健壮性

public static boolean find(int target, int[][] array) {
    //校验数组是否为空
    if (array == null || array.length == 0) {
        return false;
    }
    //校验二维数组中的所有子数组是否有空
    for (int[] arr : array) {
        if (arr == null || arr.length == 0) {
            return false;
        }
    }
    
    //从右上角开始
    int x = 0, y = array[0].length - 1;
    while (array[x][y] != target) {
        if (array[x][y] > target) {
            y--;
        }else {
            x++;
        }
        //每移动一次,就要校验指针坐标是否已越出数组边界
        if (x >= array.length || y < 0) {
            return false;
        }
    }
    //只要出了循环,代表找到了
    return true;
}

到此为止,原题目已经解答完毕。

但是,我们说这个系列不能仅仅局限于解决原始问题,更要手动加大难度,创造更多思路和方案。所以,接下来:

2. 加大原题难度:如果数组只有行符合从小到大排序,但列不符合

比方说下面这个数组:

很明显原始方案已经不可行了!

经过与小伙伴们的头脑风暴,提出了以下几个可行的方案,但不确定是否还有更好的方案,如果小伙伴们有更好的方案,评论区欢迎大家补充,我在此表示感谢!

原始的二维数组遍历

该方法依然可行,但时间复杂度还是高,耗时长。(源码不再重复)

利用Set集合的不重复性

Set集合是无序、不重复的,所以可以利用此特性,将原二维数组的所有值放入Set中,最后检验一下目标值是否在集合中即可。

该方案的时间复杂度依然为O(n2)

public static boolean find(int target, int[][] array) {
    Set<Integer> set = new TreeSet<>();
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array[i].length; j++) {
            set.add(array[i][j]);
        }
    }
    return set.contains(target);
}

筛选+二分法查找(目前方案中最快的)

原始数组中可能存在一些行,它们根本不可能存在目标值:

1) 最小值本来就比目标值大,那后面的值肯定都比目标值大

2) 最大值本来就比目标值小,那前面的值肯定也比目标值小

基于这种特征,可以筛选掉一部分数据。

之后再依据数组的行本来就是带顺序的,可以直接使用jdk原生带的二分法搜索目标值。

public static boolean find(int target, int[][] array) {
    //1. 取出可能出现目标值的列索引集合
    List<Integer> indexList = new ArrayList<>();
    for (int i = 0; i < array.length; i++) {
        int rowFirstValue = array[i][0];
        int rowLastValue = array[i][array[i].length - 1];
        if (rowFirstValue == target || rowLastValue == target) {
            return true;
        }else if (rowFirstValue < target && rowLastValue > target) {
            indexList.add(i);
        }
    }
    //2. 二分法查找
    for (Integer index : indexList) {
        int searchResult = Arrays.binarySearch(array[index], target);
        if (searchResult >= 0) {
            return true;
        }
    }
    //出了for,就代表真的没查到。。。
    return false;
}

附:jdk中自带的Arrays.binarySearch方法的核心源码

// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
                                 int key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

(完)

评论:

1 条评论,访客:1 条,站长:0 条

发表评论