相关阅读:
微信平台:153. Find Minimum in Rotated Sorted Array
简书:153. Find Minimum in Rotated Sorted Array
162. 寻找峰值
1. 描述
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。
数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
2. 理解
- 元素是否整体有序--no
不是整体有序无法采用折半查找,直接查找不容易解决 - 可以采用顺序遍历 命中特征是什么?
峰值元素是指其值大于左右相邻值的元素 这个不是充分条件
假如是最后一个元素,考虑最后一个元素越界问题。
假如 相同元素 比较没有作用,顺序遍历需要做很多判断 - 假如数组i 随便一个元素,i-1 必然存在(数组元素大约等于2)
i+1不确定了
array(i)>array(i-1)
这说明array(i-1)肯定不是peak ,因为还有比他大的
array(i)又可能是
array(i)<array(i-1)
array(i)肯定不是最大值,
array(i-1)又可能是
array(i)==array(i-1)
无法排除了,左右2个都可能出现。
还是根据题目要求寻找peak元素就是最大的。
- 元素相同的时候,还是两两比较。小的肯定不是
array[begin] <=array[i] array[begin] 肯定不是
array[end] <=array[i] array[end] 肯定不是
- 剩余的元素就是答案 最简单情况 only one
3. 测试
-
数据相等
image.png -
简单数据
image.png
升序
4. code
c++
class Solution {
public:
int findPeakElement(vector<int>& nums) {
int begin=0;
int end =nums.size()-1;
int mid=0;
while((end-begin)>1){
mid=(begin+end)/2;
if (nums[mid]>nums[mid-1]){
begin=mid;
}else if(nums[mid]<nums[mid-1]) {
end=mid-1;
}else if(nums[mid] ==nums[mid-1]){
if (nums[mid] >=nums[begin])
{
begin++;
}
if (nums[mid] >=nums[end])
{
end--;
}
}
}
return nums[begin]>=nums[end]?begin:end;
}
};
执行用时: 4 ms, 在Find Peak Element的C++提交中击败了99.63% 的用户
go
/**
time:nlog(n)
space:o(1)
执行用时: 4 ms, 在Find Peak Element的Go提交中击败了100.00% 的用户
**/
func findPeakElement(nums []int) int {
start:=0;
end:=len(nums)-1;
mid:=0
//quit
for (end-start)>1{
mid=(start+end)/2
if nums[mid]>nums[mid-1]{
start=mid//升序特点 array(mid)>array(mid-1)>array(mid-2)
}else if nums[mid]<nums[mid-1]{
end=mid-1; //降序特点 array(mid)<array(mid-1)<array(mid-2)
}else if nums[mid]<nums[mid-1]{
//仍然使用排除法
if nums[mid]>=nums[start]{
start=start+1
}
if nums[mid]>=nums[end]{
end=end-1;
}
}
}
if nums[start]>=nums[end]{
return start
}
return end
}
网友评论