找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2410|回复: 6
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Find Peak Element】-【刷题第一弹2014】

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-5-2014 06:56 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
快速通道:
https://oj.leetcode.com/problems/find-peak-element/

题目:找到数组中的peak元素,返回它的下标。peak元素为比neighbour元素数值大的元素。


建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-5-2014 07:00 PM | 显示全部楼层
本帖最后由 cpcs 于 12-5-2014 08:23 PM 编辑

[cpcs解法]

思路:
首先 peak element一定存在,因为相邻元素都不等,所以全局最大的元素一定是一个peak element……证明了存在性
我们先看一下序列开头和结尾的元素 为了方便,我们还是带上num[-1]和num[n],则num[-1] < num[0], num[n - 1] > num[n]。所以从序列真实两边的元素看不等号的方向是(> , >)。
我们的结论是 满足(> ,>)的序列一定有peak element。
那么,我们二分[left,right]且该区间满足num[left] > num[left - 1] 且 num[right] > num[right + 1]则我们看一下mid = (left + right) / 2的4种符号可能性:
(1) (> ,>) 即num[mid] > num[mid - 1], num[mid] > num[mid + 1], 显然mid是一个peak element
(2) (>, <) 即num[mid] > num[mid - 1], num[mid] < num[mid + 1], 则[mid + 1.. right]满足 (>,>) 的符号要求
(3) (<, >) 即num[mid] < num[mid - 1], num[mid] > num[mid + 1], 则[left..mid - 1] 满足(>,>)的符号要求
(4) (< ,<) 即num[mid] < num[mid - 1], num[mid] < num[mid + 1], 则[left..mid - 1]和[mid + 1..right]都满足(>,>)的符号要求,走哪个区间无所谓。

时间复杂度 O(logn)。
最后return -1,如果起初数组非空的话不会执行到。

  1. class Solution {
  2. public:
  3.     int findPeakElement(const vector<int> &num) {
  4.         int n = num.size(), left = 0, right = n - 1;
  5.         while (left <= right) {
  6.             int mid = (left + right) >> 1;
  7.             if ((mid == 0) || (num[mid - 1] < num[mid])) {
  8.                 if ((mid + 1 == n) || (num[mid + 1] < num[mid])) {
  9.                     return mid;
  10.                 }   
  11.                 left = mid + 1;
  12.             }
  13.             else {
  14.                 right = mid - 1;
  15.             }
  16.             
  17.         }
  18.         return -1;
  19.     }
  20. };
复制代码


回复 支持 反对

使用道具 举报

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-5-2014 07:01 PM | 显示全部楼层
nuswufei 原始讨论贴 链接在此
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表