LeetCode题练习与总结:寻找峰值--162
一、题目描述
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组 nums
,找到峰值元素并返回其索引。数组可能包含多个峰值,在这种情况下,返回 任何一个峰值 所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞
。
你必须实现时间复杂度为 O(log 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。
提示:
1 <= nums.length <= 1000
-2^31 <= nums[i] <= 2^31 - 1
- 对于所有有效的
i
都有nums[i] != nums[i + 1]
二、解题思路
- 初始化左指针left为0,右指针right为nums.length - 1。
- 在二分查找的过程中,比较中间位置mid的元素与mid+1位置的元素: a. 如果nums[mid] > nums[mid + 1],说明峰值在mid左边(包含mid位置),将right赋值为mid。 b. 如果nums[mid] < nums[mid + 1],说明峰值在mid右边(不包含mid位置),将left赋值为mid+1。
- 重复步骤2,直到left >= right。
- 返回left位置的元素即为峰值。
三、具体代码
class Solution {
public int findPeakElement(int[] nums) {
int left = 0, right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > nums[mid + 1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
- 二分查找算法的时间复杂度通常是 O(log n),其中 n 是数组或搜索空间的长度。
- 在这个问题中,我们使用二分查找来缩小可能的峰值位置的范围。
- 在每次迭代中,我们将搜索空间减半,因此迭代次数是 log n。
- 因此,这个算法的时间复杂度是 O(log n)。
2. 空间复杂度
- 空间复杂度主要取决于算法使用的额外空间。
- 在这个问题中,我们只使用了几个额外的变量(left, right, mid),不管输入数组的大小如何,这些变量的空间占用是常数级别的。
- 因此,这个算法的空间复杂度是 O(1),即常数空间复杂度。
综上所述,该代码的时间复杂度是 O(log n),空间复杂度是 O(1)。
五、总结知识点
-
二分查找算法:这是一种高效的查找算法,它通过不断将搜索区间减半来快速定位目标值的位置。二分查找适用于有序数组或者具有特定性质的数组。
-
循环条件:
while (left < right)
是二分查找的标准循环条件,用于控制查找过程,直到找到目标值或者搜索区间为空。 -
中间位置的计算:
int mid = left + (right - left) / 2;
是计算中间位置的常见方式,它避免了直接使用(left + right) / 2
可能导致的整数溢出问题。 -
比较和区间调整:
if (nums[mid] > nums[mid + 1])
用于比较中间位置的元素与其右侧邻居的大小关系,从而决定峰值可能存在的区间。如果中间元素大于其右侧邻居,说明峰值在左侧,否则在右侧。 -
指针的更新:
right = mid;
和left = mid + 1;
分别用于更新搜索区间的左右边界。这取决于比较的结果,如果中间元素大,则保留左侧区间;如果中间元素小,则保留右侧区间。
以上就是解决这个问题的详细步骤,希望能够为各位提供启发和帮助。
原文地址:https://blog.csdn.net/weixin_62860386/article/details/140028715
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!