Java实现#寻找峰值#

寻找峰值

http://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76

从此题中得到的小感悟 :充分把握题意方能选用更合适的解题方法(类二分法)

  • 此题难度中等,很容易想到思路1,但是仅此的话,不符合“中等”的标签;另外,题中要求时间复杂度为 O(log n),这让我们很自然地联想到二分法,我们所熟悉的二分法是基于有序表,这道题目数组并不一定有序,那又如何和二分法产生关联呢?读题!读题!读题!分析题目!

思路1:模拟。

  • 遍历nums,对于nums[i],检查满足 nums[i] > nums[i-1]并且nums[i] > nums[i+1]的情况,返回下标i即可。
  • 需要注意的是,边界情况。题目给定nums[-1] = nums[n] = -∞,所以nums[0] > nums[1] 或 nums[n-1] > nums[n-2]也为峰值

复杂度

  • 时间复杂度O(n),空间复杂度O(1)

代码(Java实现)

public class Solution {
	public int findPeakElement (int[] nums) {
        int n=nums.length;
        if(n==1) return 0;
        if(n>=2) { //左边界和右边界单独判断
        	if(nums[0]>nums[1])   return 0;
        	if(nums[n-1]>nums[n-2]) return n-1;
        }
        for(int i=1;i<=n-2;i++) {
        	if(nums[i]>nums[i-1]&&nums[i]>nums[i+1]) return i;
        }
        
        return -1;
    }
}

思路2:类二分法.(比较简洁且符合要求)

借鉴了《画解剑指 Offer》作者大鹏的思路。 链接:https://leetcode-cn.com/problems/find-peak-element/solution/hua-jie-suan-fa-162-xun-zhao-feng-zhi-by-guanpengc/

我把它称之为类二分法,就是类似二分法的意思,而不把它称之为二分法,区别严格意义上的二分法

过程:

  • 首先要注意题目条件,在题目描述中出现了 nums[-1] = nums[n] = -∞,这就代表着 只要数组中存在一个元素比相邻元素大,那么沿着它一定可以找到一个峰值
  • 根据上述结论,我们就可以使用二分查找找到峰值.
  • 查找时,左指针 left,右指针 right,以其保持左右顺序为循环条件.
  • 根据左右指针计算中间位置 mid,并比较 mid 与 mid+1 的值,如果 mid 较大,则左侧存在峰值,right = mid,如果 mid + 1 较大,则右侧存在峰值,left = mid + 1 .
  • 一定要好好理解和体会上面第一句话的表达,

复杂度

  • 时间复杂度O(log n),空间复杂度O(1)

代码(Java实现)

public class Solution {
	public int findPeakElement (int[] nums) {
       int left=0,right=nums.length-1;
		int mid=0;
		while(left<right) {
		    mid=left+(right-left)/2;//增量式取区间中点
			if(nums[mid]<nums[mid+1]) left=mid+1;//右侧存在峰值
			else right=mid;//左侧存在峰值
		}
		return left;
    }
}

Q:

  • 对于思路2中的代码,有小伙伴可能有 疑惑:if 判断中 mid+1 不加限制难道不会越界吗?

A:

  • 答案是不会越界。首先你能提出这样的问题,祝贺爱思考问题,下面我会用数学知识证明 mid+1不会发生数组下标越界,不需要加以限制。
数学证明:

alt

这下明白了吧

全部评论

相关推荐

06-02 15:17
门头沟学院 Java
心爱的idea:怎么会呢 应该是打招呼有问题 问就说实习6个月全国可飞随时到岗
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
找个工作&nbsp;学历是要卡的&nbsp;要求是高的&nbsp;技能不足是真的&nbsp;实习经验是0的&nbsp;简历无处可写是事实的&nbsp;钱不好赚是真的&nbsp;想躺平又不敢躺&nbsp;也不甘心躺&nbsp;怕自己的灵感和才华被掩埋甚至从未被自己发现&nbsp;又质疑自己是否真正有才华
码农索隆:你现在啊,你心里都明白咋回事,但是你没办法改变现状,一想到未来,你又没有信心狠下心来在当下努力。 得走出这种状态,不能一直困在那里面,哪不行就去提升哪,你一动不动那指定改变不了未来,动起来,积少成多才能越来越好
点赞 评论 收藏
分享
评论
7
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务