A peak element is an element that is greater than its neighbors.
Given an input array wherenum[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 anyone of the peaks is fine.
You may imagine thatnum[-1] = num[n] = -∞.
For example, in array[1, 2, 3, 1], 3 is apeak element and your function should return the index number 2.
click to showspoilers.
Note:
Your solution should be in logarithmic complexity.
Credits:Special thanks to@tsfor adding this problem and creating all testcases.
HideTags
ArrayBinary Search
注意：
0。。。。。。。。。media1，media2。。。。。。。。n-1
二分的区间是：0。。。。。。。。。media1，media2 和media1，media2。。。。。。。。n-1
若分为0。。。。。。。。。media 和media。。。。。。。。n-1
则media为peak element的情况就被忽略了
另外，头尾添加负无穷构造新数组时要考虑溢出。
另另外：
#pragma once#include<iostream>#include<vector>using namespace std;//取大值int max(int a, int b){if (a > b)return a;return b;}int findIt(long long *list, int begain, int end){if (end – begain + 1 <= 6)//小到这种程度，遍历检查，作为递归出口{for (int i = begain; i <= end – 2; i++)//注意，是end-2if (list[i] > list[i + 1])continue;elseif (list[i + 1] > list[i + 2])return i;//注意，return的不是i+1，因为list中下标都比num中大1elsecontinue;return -1;//for循环结束，为找到，返回-1}int media1 = (begain + end) / 2;int media2 = media1 + 1;//中间两个元素的下标int aheadmedia = (begain + media2) / 2;//前半段中间元素的下标int behindmedia = (media1 + end) / 2;//后半段中间元素的下标if (list[aheadmedia] > list[begain] && list[aheadmedia] > list[media2])//前半段一定有return findIt(list, begain, media2);else if (list[behindmedia] > list[media1] && list[behindmedia] > list[end])//前半段没有，后半段一定有return findIt(list, media1, end);else//前后都不一定有，但一定有一个有，返回大的，，因为没有的话返回-1return max(findIt(list, begain, media2), findIt(list, media1, end));}int findPeakElement(const vector<int> &num) {long long *list = new long long[num.size() + 2];//list[0] = num[0] – 1;//模拟头是负无穷//注意，当num[0]为 – 2147483648时，上面写法list[0]会变成2147483647，因为num是int型的，会溢出。应下面这样写。list[0] = num[0];list[0]–;//注意！！！！！！！若list为int减1后int可能溢出，所以list应为long long类型！！！！long在32位编译器中也是4位，所以应用long longlist[num.size() + 1] = num[num.size() – 1];list[num.size() + 1]–;//模拟头是负无穷for (int i = 0; i < (int)num.size(); i++)list[i + 1] = num[i];//至此，头尾为正无穷的新数组构造完毕return findIt(list, 0, num.size() + 1);}void main(){vector<int> num;num.push_back(-2147483647-1);//不能直接push -2147483648 ,若这样，自动识别-2147483648为无符号的，不能将-号应用于无符号类型cout << "The peak element`s index in num is " << findPeakElement(num) << endl;system("pause");}
然后拍一些美得想哭的照片，留给老年的自己。
