《leetCode》：Find Peak Element

本文主要是介绍《leetCode》：Find Peak Element，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

A peak element is an element that is greater than its neighbors.Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.You may imagine that num[-1] = num[n] = -∞.For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

思路

从头至尾遍历一下，遇到满足条件的就返回，时间复杂度为O(n).

实现代码如下：

int findPeakElement(int* nums, int numsSize) {if(nums==NULL||numsSize<1){return -1;}if(numsSize==1){return 0;}//遍历一遍数组来寻找a peak numfor(int i=0;i<numsSize;i++){if(i==0&&nums[i]>nums[i+1]||i==numsSize-1&&nums[i]>nums[i-1]){return i;}else{if(nums[i-1]<=nums[i]&&nums[i]>=nums[i+1]){return i;}}} return -1;
}

思路二

在讨论区域看到了另外一种思路，利用二分查找来做的，开始看到的时候的第一反应：这个数组又没有说是先递增然后递减的数组。仔细看了下题目，原来题目Given an input array where num[i] ≠ num[i+1]暗示了就是这种情况：只是在数组中不只只有一次的递增和递减。

因此，确实是可以利用二分查找来做的。

实现代码如下：

int findPeakElement(int* nums, int numsSize) {if(nums==NULL||numsSize<1){return -1;}int left=0;int right=numsSize-1;while(left<right){//不能这样写 int mid=left+(right-left)>>1;因为算术云算法的优先级大于 移位运算符 int mid=left+((right-left)>>1);if(nums[mid]<nums[mid+1]){left=mid+1;}else{right=mid;}}return right;   
}

在实现的过程中，遇到了一个问题：
当求中位数的时候，采用了如下的代码：

int mid=left+(right-left)>>1;

发现这根本不能够求出中位数，分析了下，原来是优先级的问题，算术运算符的优先级是大于移位运算符的。因此，就出现了bug。

这篇关于《leetCode》：Find Peak Element的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---