題目描述
峰值元素是指其值大于左右相鄰值的元素，
給定一個輸入陣列 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并回傳其索引，
陣列可能包含多個峰值，在這種情況下，回傳任何一個峰值所在位置即可，
你可以假設 nums[-1] = nums[n] = -∞，
示例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函式應該回傳其索引 2，
示例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函式可以回傳索引 1，其峰值元素為 2；
或者回傳索引 5， 其峰值元素為 6，
說明:
你的解法應該是 O(logN) 時間復雜度的，
通過的代碼
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int left=0;
int right=nums.size()-1;
int mid;
if(nums.size()==1||(nums.size()==2&&nums[0]>nums[1]))
return 0;
if(nums.size()==2&&nums[0]<nums[1])
return 1;
while(left<=right)
{
mid=(left+right)/2;
if(mid!=0&&mid!=(nums.size()-1))
{
if(nums[mid]>nums[mid-1]&&nums[mid]>nums[mid+1])
return mid;
else if(nums[mid]>nums[mid-1]&&nums[mid]<nums[mid+1])
left=mid+1;
else if(nums[mid]<nums[mid-1]&&nums[mid]>nums[mid+1])
right=mid-1;
else
{
if(nums[mid-1]>nums[mid+1])
right=mid-1;
else
left=mid+1;
}
}
if(mid==0||mid==(nums.size()-1))
break;
}
mid=max_element(nums.begin(),nums.end())-nums.begin();
return mid;
}
};
解題思路
這道題目，剛開始看到時間復雜度為O(logn)我就知道應該是用二分法，但是想了很久也沒想清楚怎么用二分法，之后看了別人的題解，才發現自己漏掉了最重要的一個條件nums[-1] = nums[n] = -∞，這個條件的含義就是，這個輸入陣列的最左邊和最右邊的數字都是無窮小的，那么每次在二分的時候，如果二分位置的數字不是最大的，那就說明要繼續二分，之后尋找左右兩邊數字較大的位置作為下一個二磁區間的一個邊界（這里就是最難理解的，因為陣列最左側和最右側都是無窮小的，所以新的二磁區間不可能會一直遞增，中間必定會有遞減的部分，所以必定存在峰值），
記錄這道題，之后再來做，下次一定不要糾結太多了，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/103223.html
標籤：AI