leetcode----162. Find Peak Element
程序员文章站
2022-06-17 18:33:53
...
链接:
https://leetcode.com/problems/find-peak-element/
大意:
返回一个数组的峰顶值所在的位置。一个数组的峰顶值:该值大于其左右两边相邻的两个元素。规定:nums[0]左边和nums[nums.length - 1]右边可以认为是Integer.MIN_VALUE。例子:
思路:
顺序遍历,找到第一个降序的点即可。
代码:
class Solution {
public int findPeakElement(int[] nums) {
if (nums.length <= 1)
return 0;
int i = 0;
// 找到第一个降序的点
while (i + 1 < nums.length && nums[i] < nums[i + 1]) {
i++;
}
return i == nums.length ? i - 1 : i;
}
}
结果:
结论:
刚才又认真地看了遍题目,说是最好用对数复杂度解决,自己的方法是线性复杂度,有待改进。
最佳:(基于二分查找)
class Solution {
public int findPeakElement(int[] nums) {
//easy solution is O(n)
//How to use binary search
int l = 0, r = nums.length-1;
while ( l < r ) {
//System.out.println(l + " " + r);
int m = (l+r)/2;
int m1 = m+1;
int m2 = m > 0 ? m-1 : m;
//Find the target that bigger that its neighbor
if ( nums[m] > nums[m1] && nums[m] >= nums[m2] ) {
return m;
} else if ( nums[m] > nums[m1] ) {
r = m;
}
// Actually can go either ways if both nums[m] lesser than both its neighbor. For the sake of simplicity, we go right so we don't need to check for other condition.
else
l = m1;
}
//since we check with m+1, need to return l
return l;
}
}
推荐阅读
-
cvc-elt.1: Cannot find the declaration of element 'beans'Failed to read schema document 'http://www.springframework.org/schema/beans/sprin
-
第七章第十题(找出最小元素的下标)(Find the subscript of the smallest element)
-
刷题记录(Find Peak Element Solution)
-
75. Find Peak Element
-
162. Find Peak Element**
-
leetcode(162):寻找峰值 Find Peak Element
-
leetcode----162. Find Peak Element
-
Find First and Last Position of Element in Sorted Array
-
cvc-elt.1: Cannot find the declaration of element 'beans'Failed to read schema document 'http://www.springframework.org/schema/beans/sprin
-
第七章第十题(找出最小元素的下标)(Find the subscript of the smallest element)