高频面试题：找出峰值元素

你好戴先生

发布于 2022-05-16 07:33:03

54100

代码可运行

运行总次数：0

代码可运行

大家好，我是戴先生今天给大家介绍一下如何利用玄学二分法找出峰值元素想直奔主题的可直接看思路3 题目给定一个整数数组求出数组中任一峰值元素的索引地址i 注意： 1、峰值元素是指其值严格大于左右相邻值的元素 2、对于所有有效的 i 都有 nums[i] != nums[i + 1] 3、如果存在多个峰值元素，返回任一峰值元素索引即可

题解

根据题目，峰值元素其实就是将数组转换为坐标轴函数之后的极大值

可以简单地归为以下三种情况

第一种情况就是数组是单调递增或递减的

这种情况只存在一个峰值元素，为数值7

第二种情况数组先单调递减（增），再单调递增（减）

这种情况存在两（一）个峰值元素

为数值7，7（5）

第三种情况数组存在多个单调递增和递减的区间

这种情况存在多个峰值元素

为数值4，7，4

思路1

高中数学告诉我们：最大值一定是极大值

所以很简单了

只要求出数组中的最大值就可以了

求出最大值的方法就多了

最简单的就是遍历所有元素

代码实现1

思路1的代码实现如下

    public static int findPeekElement1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int result = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[result]) {
                result = i;
            }
        }

        return result;
    }

思路2

在思路1的基础上我们可以做一下优化

题目要求我们找出任一极大值即可

所以我们在遍历数组的时候

只要找到了符合条件（大于左边和右边的值）的数

就能直接返回结果了

唯一需要注意的是首、尾两个值的情况

因为这两个值是没有“左边”或“右边”的值

所以如果在除了首尾之外的元素中没有找到符合条件的值

只需要比较一下首尾两个值，较大者即为极大值，且是最大值

代码实现2

思路2的代码实现如下

    public static int findPeekElement1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        for (int i = 1; i < nums.length - 1; i++) {
            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return nums[0] >= nums[nums.length - 1] ? 0 : nums.length - 1;
    }

思路3

思路1和思路2的时间负责都都是O(n)

那么有没有办法将时间复杂度优化一下呢？

给大家说一个思路

凡是遇到有序数据或有规律的区间有序数组

第一个可以尝试的方法就是玄学算法：二分法

如图所示

通过二分法找到第一个中间值mid的时候

如果nums[mid -1] < nums[mid]

那么mid或mid的右侧一定存在一个极大值

那么就可以将范围锁定到mid~end之间

同理

如果如果nums[mid -1] > nums[mid]

那么在mid或者mid的左侧必然存在一个极大值

那么就可以将范围锁定到start~mid之间

思路明确之后代码就很好实现了

而且二分算法的时间复杂度为log(n)

代码实现3

思路3的代码实现如下

    public static int findPeekElement2(int[] nums) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int start = 0;
        int end = nums.length - 1;
        int mid;
        while (start + 1 < end) {
            mid = (start + end) / 2;
            if (nums[mid - 1] > nums[mid]) {
                end = mid;
            } else if (nums[mid + 1] > nums[mid]) {
                start = mid;
            } else {
                return mid;
            }
        }
        return nums[start] > nums[end] ? start : end;
    }