乐趣区

关于算法:二分搜索怎么用我和快手面试官进行了深度探讨

读完本文,你不仅学会了算法套路,还能够顺便去 LeetCode 上拿下如下题目:

410. 宰割数组的最大值

———–

常常有读者问我,读了之前的爆文 二分查找框架详解 之后,二分查找的算法他写的很溜了,但仅仅局限于在数组中搜寻元素,不晓得底怎么在算法题外面使用二分查找技巧来优化效率。

那我先说论断,你想用二分查找技巧优化算法,首先要把 for 循环模式的暴力算法写进去,如果算法中存在如下模式的 for 循环

// func(i) 是 i 的枯燥函数(递增递加都能够)int func(int i);

// 形如这种 for 循环能够用二分查找技巧优化效率
for (int i = 0; i < n; i++) {if (func(i) == target)
        return i;
}

如果 func(i) 函数是在 i 上枯燥的函数,肯定能够应用二分查找技巧优化 for 循环

「在 i 上枯燥的函数」是指 func(i) 的返回值随着 i 的减少而减少,或者随着 i 的减少而减小。

为什么满足这个条件就能够应用二分查找?因为这个逻辑和「在有序数组中查找一个元素」是齐全一样的呀

有序数组 nums 中查找某一个数 target,是不是最简略二分查找模式?咱们看下一般的 for 循环遍历算法:

// nums 是一个有序数组
int[] nums;
// target 是要搜寻的元素
int target;

// 搜寻 target 在 nums 中的索引
for (int i = 0; i < nums.length; i++) {if (nums[i] == target)
        return i;
}

既然 nums 是有序数组,你把 nums[i] 看做函数调用,是不是能够了解为 nums 在参数 i 上是枯燥的?这是不是和之前说的 func(i) 函数齐全一样?

当然,前文 二分查找框架详解 说过,二分查找算法还有搜寻左侧、右侧边界的变体,怎么使用到具体算法问题中呢?

还是留神察看 for 循环模式,只是不肯定是 func(i) == target 作为终止条件,可能是 <= 或者 >= 的关系,这个能够依据具体的题目意思来推断,咱们实操一下力扣第 410 题「宰割数组的最大值」,难度 Hard

函数签名如下:

int splitArray(int[] nums, int m);

这个题目有点相似前文一道经典动静布局题目 高楼扔鸡蛋,题目比拟绕,又是最大值又是最小值的。

简略说,给你输出一个数组 nums 和数字 m,你要把 nums 宰割成 m 个子数组。

必定有不止一种宰割办法,每种宰割办法都会把 nums 分成 m 个子数组,这 m 个子数组中必定有一个和最大的子数组对吧。

咱们想要找一个宰割办法,该办法宰割出的最大子数组和是所有办法中最大子数组和最小的。

请你的算法返回这个宰割办法对应的最大子数组和。

我滴妈呀,这个题目看了就感觉 Hard,齐全没思路,这题怎么能和二分查找算法扯上关系?

说个小插曲,快手面试有一道画师画画的算法题,很难,就是以这道题为原型。过后我没做过这道力扣题,面试有点懵,不过之前文章 二分查找算法使用 写了两道相似的比较简单的题目,外加面试官的提醒,把那道题做进去了。

面试做算法题的时候,题目个别都会要求算法的工夫复杂度,如果你发现 O(NlogN) 这样存在对数的复杂度,个别都要往二分查找的方向上靠,这也算是个小套路

言归正传,如何解决这道数组宰割的问题?

首先,一个拍脑袋的思路就是用 回溯算法框架 暴力穷举呗,我简略说下思路:

你不是要我把 nums 宰割成 m 个子数组,而后计算巴拉巴拉又是最大又是最小的那个最值吗?那我把所有宰割计划都穷举进去,那个最值必定能够算进去对吧?

怎么穷举呢?把 nums 宰割成 m 个子数组,相当于在 len(nums) 个元素的序列中切 m - 1 刀,对于每两个元素之间的间隙,咱们都有两种「抉择」,切一刀,或者不切。

你看,这不就是规范的回溯暴力穷举思路嘛,咱们依据穷举后果去计算每种计划的最大子数组和,必定能够算出答案。

然而回溯的毛病就是复杂度很高,咱们方才说的思路其实就是「组合」嘛,工夫复杂度就是组合公式:

工夫复杂度其实是十分高的,所以回溯算法不是一个好的思路,还是得上二分查找技巧,反向思考这道题。

当初题目是固定了 m 的值,让咱们确定一个最大子数组和;所谓反向思考就是说,咱们能够反过来,限度一个最大子数组和 max,来反推最大子数组和为 max 时,至多能够将 nums 宰割成几个子数组

比如说咱们能够写这样一个 split 函数:

// 在每个子数组和不超过 max 的条件下,// 计算 nums 至多能够宰割成几个子数组
int split(int[] nums, int max);

比如说 nums = [7,2,5,10],若限度 max = 10,则 split 函数返回 3,即 nums 数组起码能宰割成三个子数组,别离是 [7,2],[5],[10]

那如果咱们找到一个最小 max 值,满足 split(nums, max)m 相等,那么这个 max 值不就是合乎题意的「最小的最大子数组和」吗?

当初就简略了,咱们只有对 max 进行穷举就行,那么最大子数组和 max 的取值范畴是什么呢?

显然,子数组至多蕴含一个元素,至少蕴含整个数组,所以「最大」子数组和的取值范畴就是闭区间 [max(nums), sum(nums)],也就是最大元素值到整个数组和之间。

那么,咱们就能够写出如下代码:

/* 主函数,计算最大子数组和 */
int splitArray(int[] nums, int m) {int lo = getMax(nums), hi = getSum(nums);
    for (int max = lo; max <= hi; max++) {
        // 如果最大子数组和是 max,// 至多能够把 nums 宰割成 n 个子数组
        int n = split(nums, max);
        // 为什么是 <= 不是 ==?if (n <= m) {return max;}
    }
    
    return -1;
}

/* 辅助函数,若限度最大子数组和为 max,计算 nums 至多能够被宰割成几个子数组 */
int split(int[] nums, int max) {
    // 至多能够宰割的子数组数量
    int count = 1;
    // 记录每个子数组的元素和
    int sum = 0;
    for (int i = 0; i < nums.length; i++) {if (sum + nums[i] > max) {
            // 如果以后子数组和大于 max 限度
            // 则这个子数组不能再增加元素了
            count++;
            sum = nums[i];
        } else {
            // 以后子数组和还没达到 max 限度
            // 还能够增加元素
            sum += nums[i];
        }
    }
    return count;
}

// 计算数组中的最大值
int getMax(int[] nums) {
    int res = 0;
    for (int n : nums)
        res = Math.max(n, res);
    return res;
}

// 计算数组元素和
int getSum(int[] nums) {
    int res = 0;
    for (int n : nums)
        res += n;
    return res;
}

这段代码有两个关键问题:

1、对 max 变量的穷举是从 lohi 即从小到大的

这是因为咱们求的是「最大子数组和」的「最小值」,且 split 函数的返回值有枯燥性,所以从小到大遍历,第一个满足条件的值就是「最小值」。

2、函数返回的条件是 n <= m,而不是 n == m。依照之前的思路,应该 n == m 才对吧?

其实,split 函数采纳了贪婪的策略,计算的是 max 限度下 至多 可能将 nums 宰割成几个子数组。

举个例子,输出 nums = [2,1,1], m = 3,显然宰割办法只有一种,即每个元素都认为是一个子数组,最大子数组和为 2。

然而,咱们的算法会在区间 [2,4] 穷举 max,当 max = 2 时,split 会算出 nums 至多 能够被宰割成 n = 2 个子数组 [2][1,1]

max = 3 时算出 n = 2,当 max = 4 时算出 n = 1,显然都是小于 m = 3 的。

所以咱们不能用 n == m 而必须用 n <= m 来找到答案,因为如果你能把 nums 宰割成 2 个子数组([2],[1,1]),那么必定也能够宰割成 3 个子数组([2],[1],[1]

好了,当初 for 循环的暴力算法曾经写完了,然而无奈通过力扣的判题零碎,会超时。

因为 split 是枯燥函数,且合乎二分查找技巧进行优化的标记,所以能够试图革新成二分查找。

那么应该应用搜寻左侧边界的二分查找,还是搜寻右侧边界的二分查找呢?这个还是要看咱们的算法逻辑:

int lo = getMax(nums), hi = getSum(nums);
for (int max = lo; max <= hi; max++) {int n = split(nums, max);
    if (n <= m) {return max;}
}

可能存在多个 max 使得 split(nums, max) 算出雷同的 n因为咱们的算法会返回最小的那个 max,所以应该应用搜寻左侧边界的二分查找算法

当初,问题变为:在闭区间 [lo, hi] 中搜寻一个最小的 max,使得 split(nums, max) 恰好等于 m

那么,咱们就能够间接套用搜寻左侧边界的二分搜寻框架改写代码:

int splitArray(int[] nums, int m) {
    // 个别搜寻区间是左开右闭的,所以 hi 要额定加一
    int lo = getMax(nums), hi = getSum(nums) + 1;
    while (lo < hi) {int mid = lo + (hi - lo) / 2;
        // 依据宰割子数组的个数膨胀搜寻区间
        int n = split(nums, mid);
        if (n == m) {
            // 膨胀右边界,达到搜寻左边界的目标
            hi = mid;
        } else if (n < m) {
            // 最大子数组和下限高了,减小一些
            hi = mid;
        } else if (n > m) {
            // 最大子数组和下限低了,减少一些
            lo = mid + 1;
        }
    }
    return lo;
}

int split(int[] nums, int max) {/* 见上文 */}
int getMax(int[] nums) {/* 见上文 */}
int getSum(int[] nums) {/* 见上文 */}

这段二分搜寻的代码就是规范的搜寻左侧边界的代码框架,如果不了解能够参见前文 二分查找框架详解,这里就不开展了。

至此,这道题就通过二分查找技巧高效解决了。假如 nums 元素个数为 N,元素和为 S,则 split 函数的复杂度为 O(N),二分查找的复杂度为 O(logS),所以算法的总工夫复杂度为 O(N*logS)

退出移动版