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

点击上方蓝字设为星标从 O(N) 优化到 O(logN),你的第一想法是什么?

下面开始今天的学习~

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

今天分享的题目来源于 LeetCode 第 162 号问题:寻找峰值。通过这道题目,你又能再次复习二分法的用处。

题目描述

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

给定一个输入数组 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;
}


END



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

● 答应我,别再if/else走天下了可以吗

● 如何利用寒假的时间来准备2020年的蓝桥杯?

● 给大家推荐一款软件

关于计算机读研的小建议


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


点“在看你懂得 

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

原文始发于微信公众号(五分钟学算法):从 O(N) 优化到 O(logN),你的第一想法是什么?

本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 从 O(N) 优化到 O(logN),你的第一想法是什么?

我还会在以下平台发布内容

GitHub 哔哩哔哩