【前言】
今天是力扣打卡第7天！
好快呀，一周已經過去了，鐵汁們，你們堅持下來了沒？
原題：尋找峰值
題目描述：
峰值元素是指其值嚴格大于左右相鄰值的元素，
給你一個整數陣列 nums，找到峰值元素并回傳其索引，陣列可能包含多個峰值，在這種情況下，回傳 任何一個峰值 所在位置即可，
你可以假設 nums[-1] = nums[n] = -∞ ，
你必須實作時間復雜度為 O(log n) 的演算法來解決此問題，
【敲黑板】：本題屬于查找類題型，又看到時間復雜度是O(logN)，所以不難想到二分查找
示例1：
輸入：nums = [1,2,3,1]
輸出：2
解釋：3 是峰值元素，你的函式應該回傳其索引 2，示例2：
輸入：nums = [1,2,1,3,5,6,4]
輸出：1 或 5
解釋：你的函式可以回傳索引 1，其峰值元素為 2；
或者回傳索引 5， 其峰值元素為 6，注意：
使用二分法是有要求的，前提是一定要有序！ 那么這道題目該怎么去解呢？我們也不能去把它先排個序，因為會把索引弄亂，那該咋辦呢？請朝后看...
找到了一個規律：
nums[mid] > nums[mid + 1] 時，mid前邊一定存在峰值；
nums[mid] < nums[mid + 1] 時，mid+1后邊一定存在峰值
代碼執行
int findPeakElement(int* nums, int numsSize){
//考慮特殊情況
if(nums == NULL || numsSize == 0){
return -1;
}
int left = 0;
int right = numsSize - 1;
int mid = 0;
while(left <= right){
//如果while回圈中的運算式中沒有判斷==時的情況，這條陳述句也就可以省略了
//之所以加上，是為了套用二分的那個結構，等到后面熟悉使用了就不會這樣啦
if(left == right){
return left;
}
mid = left + (right - left) / 2;
if(nums[mid] < nums[mid + 1]){
//mid+1后邊一定存在峰值
left = mid + 1;
}else{
right = mid;
//mid前邊一定存在峰值
}
}
return left;
}復雜度分析
時間復雜度：O(logN)
空間復雜度：O(1)
結語
今天是力扣打卡第7天！
感謝力扣里面的大佬，向你們學習[致敬]！！
886，咱們明兒再見！！！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/350843.html
標籤：其他
上一篇：【C++學習】—— （一）概念