从 O(N) 优化到 O(logN)，你的第一想法是什么？

五分钟学算法

发布于 2020-03-28 12:46:52

54100

代码可运行

文章被收录于专栏：五分钟学算法五分钟学算法

运行总次数：0

代码可运行

题目描述

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

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

你可以假设 nums[-1] = nums[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。

说明:

你的解法应该是 O(logN) 时间复杂度的。

题目解析

目让你找出一个数组中的 peak element，数组中可能存在一个或者多个 peak element，但是你只需要找出一个就好。

这道题目最直接的办法就是直接遍历一遍数组，然后将每个元素与其左右相邻的元素进行比较，符合条件输出即可。

显而易见，这么做时间复杂度是 O(n)，n 为数组中元素的个数。

有没有更快的方法呢？

比 O(n) 还要快的话，一般来说只会是 O(lgn) 和 O(1)，O(1) 显然是不可能的，那么就只剩下 O(lgn)。

通过这个时间复杂度，我相信你应该知道用什么样的算法，没错就是二分查找。

那么用二分查找怎么做呢？

题目描述中有一个细节是，我们可以认为 arr[-1] == arr[n] == -Inf，也就是两头的元素只需要和它相邻的一个元素比较即可。再进一步想，这里其实还隐藏了一个信息，就是我们二分查找顺着递增的方向去找的话就一定能够找到峰值。

如果能够分析到这里，那么这道题基本上就算是解决了。

动画描述

参考代码

//五分钟学算法
public int findPeakElement(int[] nums) {
    if (nums == null || nums.length == 0) {
        return -1;
    }

    int start = 0, end = nums.length - 1;
    while (start + 1 < end) {
        int mid = start + (end - start) / 2;

        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1]) {
            return mid;
        } else if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1]) {
            start = mid;
        } else {
            end = mid;
        }
    }

    if (nums[start] > nums[end]) {
        return start;
    }

    return end;
}