关于后端:常见题型总结二分以及为何能二分二段性的拓展

77次阅读

共计 2824 个字符,预计需要花费 8 分钟才能阅读完成。

题目形容

这是 LeetCode 上的 162. 寻找峰值 ,难度为 中等

Tag :「二分」

峰值元素是指其值严格大于左右相邻值的元素。

给你一个整数数组 nums,找到峰值元素并返回其索引。数组可能蕴含多个峰值,在这种状况下,返回 任何一个峰值 所在位置即可。

你能够假如 nums[-1] = nums[n] = -∞

你必须实现工夫复杂度为 $O(\log{n})$ 的算法来解决此问题。

示例 1:

输出:nums = [1,2,3,1]

输入:2

解释:3 是峰值元素,你的函数应该返回其索引 2。

示例 2:

输出:nums = [1,2,1,3,5,6,4]

输入:1 或 5 

解释:你的函数能够返回索引 1,其峰值元素为 2;或者返回索引 5,其峰值元素为 6。

提醒:

  • $1 <= nums.length <= 1000$
  • $-2^{31} <= nums[i] <= 2^{31} – 1$
  • 对于所有无效的 i 都有 nums[i] != nums[i + 1]

模仿

因为数据范畴只有 $1000$,应用线性扫描找峰值的模仿做法也是没有问题。

代码:

class Solution {public int findPeakElement(int[] nums) {
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            boolean ok = true;
            if (i - 1 >= 0) {if (nums[i - 1] >= nums[i]) ok = false;
            }
            if (i + 1 < n) {if (nums[i + 1] >= nums[i]) ok = false;
            }
            if (ok) return i;
        }
        return -1;
    }
}
  • 工夫复杂度:$O(n)$
  • 空间复杂度:$O(1)$

二分

题目让咱们实现一个 $O(\log{n})$ 算法,这是对应用「二分」的强烈暗示。

和平常的题目一样,咱们该当从是否具备「二段性」来思考是否能够进行「二分」

不难发现,如果 在确保有解的状况下,咱们能够依据以后的宰割点 $mid$ 与左右元素的大小关系来领导 $l$ 或者 $r$ 的挪动。

假如以后宰割点 $mid$ 满足关系 $num[mid] > nums[mid + 1]$ 的话,一个很简略的想法是 $num[mid]$ 可能为峰值,而 $nums[mid + 1]$ 必然不为峰值,于是让 $r = mid$,从左半局部持续找峰值。

预计不少同学靠这个思路 AC 了,只能说做法对了,剖析没对。

上述做法正确的前提有两个:

  1. 对于任意数组而言,肯定存在峰值(肯定有解);
  2. 二分不会错过峰值。

咱们别离证实一下。

证实 $1$:对于任意数组而言,肯定存在峰值(肯定有解)

依据题意,咱们有「数据长度至多为 $1$」、「越过数组两边看做负无穷」和「相邻元素不相等」的起始条件。

咱们能够依据数组长度是否为 $1$ 进行分状况探讨:

  1. 数组长度为 $1$,因为边界看做负无穷,此时峰值为该惟一元素的下标;
  2. 数组长度大于 $1$,从最右边的元素 $nums[0]$ 开始登程思考:

    • 如果 $nums[0] > nums[1]$,那么最右边元素 $nums[0]$ 就是峰值(联合左边界为负无穷);
    • 如果 $nums[0] < nums[1]$,因为曾经存在明确的 $nums[0]$ 和 $nums[1]$ 大小关系,咱们将 $nums[0]$ 看做边界,$nums[1]$ 看做新的最左侧元素,持续往右进行剖析:

      • 如果在达到数组最右侧前,呈现 $nums[i] > nums[i + 1]$,阐明存在峰值地位 $i$(当咱们思考到 $nums[i]$,必然满足 $nums[i]$ 大于前一元素的前提条件,当然前一元素可能是原始左边界);
      • 达到数组最右侧,还没呈现 $nums[i] > nums[i + 1]$,阐明数组严格递增。此时联合右边界能够看做负无穷,可断定 $nums[n – 1]$ 为峰值。

综上,咱们证实了无论何种状况,数组必然存在峰值。

证实 $2$:二分不会错过峰值

其实基于「证实 $1$」,咱们很容易就能够推理出「证实 $2$」的正确性。

整顿一下由「证实 $1$」得出的推理:如果以后地位大于其左边界或者右边界,那么在以后地位的左边或右边必然存在峰值。

换句话说,对于一个满足 $nums[x] > nums[x – 1]$ 的地位,$x$ 的左边肯定存在峰值;或对于一个满足 $nums[x] > nums[x + 1]$ 的地位,$x$ 的右边肯定存在峰值。

因而这里的「二段性」其实是指:在以 $mid$ 为宰割点的数组上,依据 $nums[mid]$ 与 $nums[mid \pm 1]$ 的大小关系,能够确定其中一段满足「必然有解」,另外一段不满足「必然有解」(可能有解,可能无解)。

如果不了解为什么「证实 $2$」的正确性能够由「证实 $1$」推导而出的话,能够重点看看「证实 $1$」的第 $2$ 点的证实。

至此,咱们证实了始终抉择大于边界一端进行二分,能够确保抉择的区间肯定存在峰值,并随着二分过程一直迫近峰值地位。

另外,为了关照还在纠结应用什么“模板”的同学,特意写了两个版本。但其实只有搞清楚咱们「二分」什么内容,基本不会存在说用哪种形式能力写过的状况。

代码:

class Solution {public int findPeakElement(int[] nums) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > nums[mid + 1]) r = mid;
            else l = mid + 1;
        }
        return r;
    }
}
class Solution {public int findPeakElement(int[] nums) {
        int n = nums.length;
        if (n == 1) return 0;
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] > nums[mid - 1]) l = mid;
            else r = mid - 1;
        }
        return r;
    }
}
  • 工夫复杂度:$O(\log{n})$
  • 空间复杂度:$O(1)$

总结

通过本题,咱们能够对「二分」有进一步的意识。

最早在 33. 搜寻旋转排序数组 中,咱们强调,二分的实质是「二段性」而非「枯燥性」,而通过本题,咱们进一步发现「二段性」还能持续细分,不仅仅只有满足 $01$ 个性(满足 / 不满足)的「二段性」能够应用二分,满足 $1?$ 个性(肯定满足 / 不肯定满足)也能够二分。

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.162 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,局部是有锁题,咱们将先把所有不带锁的题目刷完。

在这个系列文章外面,除了解说解题思路以外,还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码,我建设了相干的仓库:https://github.com/SharingSou…

在仓库地址里,你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

正文完
 0