162 Find Peak Element 尋找峰值
Description:
A peak element is an element that is greater than its neighbors.
Given an input array nums, where nums[i] ≠ nums[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 nums[-1] = nums[n] = -∞.
Example:
Example 1:
Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:
Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2, or index number 5 where the peak element is 6.
Follow up:
Your solution should be in logarithmic complexity.
題目描述:
峰值元素是指其值大于左右相鄰值的元素。
給定一個輸入數(shù)組 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
數(shù)組可能包含多個峰值，在這種情況下，返回任何一個峰值所在位置即可。
你可以假設(shè) nums[-1] = nums[n] = -∞。
示例 :
示例 1:
輸入: nums = [1,2,3,1]
輸出: 2
解釋: 3 是峰值元素，你的函數(shù)應(yīng)該返回其索引 2。
示例 2:
輸入: nums = [1,2,1,3,5,6,4]
輸出: 1 或 5
解釋: 你的函數(shù)可以返回索引 1，其峰值元素為 2；
或者返回索引 5， 其峰值元素為 6。
說明：
你的解法應(yīng)該是 O(logN) 時間復(fù)雜度的。
思路:
- 逐個搜索
搜索到第一個遞減的就是答案
時間復(fù)雜度O(n), 空間復(fù)雜度O(1) - 由于題目要求對數(shù)時間復(fù)雜度, 考慮二分法
由于數(shù)組中 nums[i] != nums[i + 1],
若nums[mid] > nums[mid + 1](注意 nums[mid] != nums[mid + 1]), 則 mid有可能是 peak, 去掉右半部分, 即 right = mid
否則, 去掉左半部分, 即 left = mid + 1
時間復(fù)雜度O(lgn), 空間復(fù)雜度O(1) - 由于最大值一定是峰值
直接返回最大值下標即可
時間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
int findPeakElement(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + ((right - left) >> 1);
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
};
Java:
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right)
{
int mid = left + ((right - left) >>> 1);
if (nums[mid] > nums[mid + 1]) right = mid;
else left = mid + 1;
}
return left;
}
}
Python:
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
return nums.index(max(nums))
