龙空技术网

牛客网高频算法题系列-BM19-寻找峰值

雄狮虎豹 166

前言:

今天你们对“peak算法及实例”大约比较关注,朋友们都想要分析一些“peak算法及实例”的相关知识。那么小编也在网摘上汇集了一些关于“peak算法及实例””的相关资讯,希望大家能喜欢,姐妹们快快来了解一下吧!

牛客网高频算法题系列-BM19-寻找峰值题目描述

给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。

峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

假设 nums[-1] = nums[n] = -\infty−∞

对于所有有效的 i 都有 nums[i] != nums[i + 1]

你可以使用O(logN)的时间复杂度实现此问题吗?

原题目见:寻找峰值

解法一:数组遍历

首先,判断几种特殊场景:

如果数组为空,则不存在峰值;

如果数组只有一个元素,因为都是负无穷,所以第一个元素即为峰值;

如果数组的第一个元素比第二个元素大,加上左边负无穷,则第一个元素必为峰值;

如果数组的最后一个元素比倒数二个元素大,加上右边边负无穷,则倒数第一个元素必为峰值。

如果不存在以上特殊情况,则从数组的第二位开始遍历数组,判断是否是峰值。

解法一:二分法

原理:因为左右都是负无穷,对于中间的元素,如果nums[mid] > nums[mid + 1],也就是mid部分递减,加上左边负无穷,所以mid的左边一定会有峰值;同理,如果nums[mid] < nums[mid + 1],加上右边负无穷,所以mid的右边一定会有峰值。

代码

public class Bm019 {    /**     * 遍历数组     *     * @param nums     * @return     */    public static int findPeakElement(int[] nums) {        // 如果数组为空,则不存在峰值        if (nums == null) {            return -1;        }        // 如果数组的长度为1,则首位即为峰值        if (nums.length == 1) {            return 0;        }        // 如果第一位比第二位大,则第一位必为峰值        if (nums[0] > nums[1]) {            return 0;        }        // 如果最后一位比倒数第二位大,则最后一位必为峰值        if (nums[nums.length - 1] > nums[nums.length - 2]) {            return nums.length - 1;        }        // 如果前面的几种特殊场景不存在,则遍历数组中的元素,逐一判断是否是峰值        for (int i = 1; i < nums.length - 1; i++) {            if (nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {                return i;            }        }        return -1;    }    /**     * 二分法     * 原理:因为左右都是负无穷,对于中间的元素,如果nums[mid] > nums[mid + 1],就是mid部分递减,加上左边负无穷,     * 所以mid的左边一定会有峰值;同理,如果nums[mid] < nums[mid + 1],加上右边负无穷,所以mid的右边一定会有峰值。     *     * @param nums     * @return     */    public static int findPeakElement2(int[] nums) {        // 如果数组为空,则不存在峰值        if (nums == null) {            return -1;        }        // 如果数组的长度为1,则首位即为峰值        if (nums.length == 1) {            return 0;        }        // 如果第一位比第二位大,则第一位必为峰值        if (nums[0] > nums[1]) {            return 0;        }        // 如果最后一位比倒数第二位大,则最后一位必为峰值        if (nums[nums.length - 1] > nums[nums.length - 2]) {            return nums.length - 1;        }        int left = 1, right = nums.length - 2;        while (left < right) {            int mid = (left + right) / 2;            if (nums[mid] > nums[mid + 1]) {                right = mid;            } else {                left = mid + 1;            }        }        return left;    }    public static void main(String[] args) {        int[] nums = {2, 4, 1, 2, 7, 8, 4};        System.out.println(findPeakElement(nums));        System.out.println(findPeakElement2(nums));    }}

1.01^{365} ≈ 37.7834343329

0.99^{365} ≈ 0.02551796445

相信坚持的力量!

标签: #peak算法及实例