LC.162.Find Peak Element-寻找峰值元素-解法论证

背景与要求:
Given a 0-indexed integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. nums[-1]=nums[n]=-∞。
给定一个0索引的整数数组nums,查找峰值元素并返回其索引。如果数组包含多个峰值,则返回任意一个峰值的索引。
其中:峰值元素严格大于其相邻元素,元素严格大于数组外的相邻元素(即nums[-1]=nums[n]=-∞),算法的时间复杂度需要是O(log n)。
限制条件:
1 <= nums.length <= 1000 -231 <= nums[i] <= 231 - 1 nums[i] != nums[i + 1] for all valid i. 测试用例1: Input: nums = [1,2,3,1] Output: 2 测试用例2: Input: nums = [1,2,1,3,5,6,4] Output: 1 or 5重点应当在于发现并证明二分查找的应用可以解决此问题,即:

1. 最基础的: 任意数组一定存在至少一个峰值;

2. 任意数组都有方法找到一个mid位置,保证一定有峰值出现在mid的一侧;

3. 通过二分查找每次都可以确定一个mid的位置。

只要能证明上面3点,就可以很快得到算法。

证明主要是通过数学逻辑:

1.1 若数组长度为1,峰值就是该唯一元素(边界外看做负无穷)

1.2 若数组长度大于1,从最左边的nums[0]开始往右查找并判断

1.2.1 若出现nums[i]nums[i+1](极端情况为最右侧的边界),则nums[i]为峰值元素

2 整理上述推论可知,一个满足nums[i]<(>)nums[i+1]的元素,其右边(左边)一定存在峰值

3 即,通过不断选择mid存在峰值的一端继续运算,可以不断逼近直至找到一个峰值

一旦完成了以上论证,代码本身就是基于二分查找(Binary Search)的框架进行调整。java实现如下:

class Solution {
    public int findPeakElement(int[] nums) {
        int n = nums.length;
		// 检查边界条件
        if(nums.length == 1) return 0;
        if(nums[0] > nums[1]) return 0;
        if(nums[n-1] > nums[n-2]) return n-1;
		// 开始二分查找
        int start = 1;
        int end = n-2;
        while(start <= 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]) end = mid - 1;
            else if(nums[mid] < nums[mid+1]) start = mid + 1;
        }
        return -1;
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注