关于java:牛客网高频算法题系列BM19寻找峰值

32次阅读

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

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

题目形容

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

  1. 峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
  2. 假如 nums[-1] = nums[n] = -\infty−∞
  3. 对于所有无效的 i 都有 nums[i] != nums[i + 1]
  4. 你能够应用 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$
置信保持的力量!

正文完
 0