天津做网站优化,哈尔滨道外区建设局官方网站,wordpress高仿公众号,加强网站内容建设的意见为了实现时间复杂度为 O ( log n ) O(\log n) O(logn)#xff0c;可以使用二分查找法#xff1a;
解题思路#xff1a;
峰值的特性是#xff1a;当前元素大于左右相邻元素。使用二分法#xff1a; 如果 nums[mid] nums[mid 1]#xff0c;说明峰值在左侧或当前…
为了实现时间复杂度为 O ( log n ) O(\log n) O(logn)可以使用二分查找法
解题思路
峰值的特性是当前元素大于左右相邻元素。使用二分法 如果 nums[mid] nums[mid 1]说明峰值在左侧或当前 mid 位置包括 mid因此将 right mid。否则峰值在右侧因此将 left mid 1。 不断收缩区间直到 left right此时即找到峰值。
时间复杂度
时间复杂度(O(\log n))因为每次迭代都将搜索范围减半。空间复杂度(O(1))不需要额外的空间。
java 实现
class Solution {public int findPeakElement(int[] nums) {int left 0, right nums.length - 1;while (left right) {int mid left (right - left) / 2;// 如果中点比右侧元素大说明峰值在左侧包括midif (nums[mid] nums[mid 1]) {right mid;} else { // 否则峰值在右侧left mid 1;}}// 最终left和right会相遇此时即为峰值位置return left;}
}数组即便不是有序的为什么仍然二分查找仍然可以找到峰值
这是因为这道题的二分查找并不依赖于数组是否有序而是利用了“峰值”的定义和数组的局部特性。
关键点 题目定义的峰值条件 峰值是指某个元素严格大于其左右邻居的元素。如果一个元素 nums[mid] nums[mid 1]那么在 mid 或者其左侧一定存在一个峰值。如果 nums[mid] nums[mid 1]那么在 mid 的右侧一定存在一个峰值。 为什么可以二分 二分查找的核心在于 每次选择一个中间点 mid并根据某个条件判断下一个搜索范围。在这道题中“峰值”可以通过比较 nums[mid] 和 nums[mid 1] 来判断范围 如果 nums[mid] nums[mid 1] 峰值在左侧或就是 mid因为 mid 本身比右边的大局部性质可以舍弃右侧部分。 如果 nums[mid] nums[mid 1] 峰值一定在右侧因为右边存在一个更大的值最终会到达一个下降点形成峰值。 这利用了“递增到下降”的局部特性来缩小搜索范围。 数学直观解释 假设数组中不存在连续相等的数字即没有平缓区域并且在数组两端可以假想有值为负无穷的元素题目已假设 nums[-1] nums[n] -∞。在数组中总能找到一个峰值元素原因是 如果数组中存在一个“上升”趋势例如 nums[i] nums[i1]那么在右侧一定有一个峰值。如果数组中存在一个“下降”趋势例如 nums[i] nums[i1]那么左侧也一定存在一个峰值。 这种趋势保证了每次二分缩小范围后最终一定会收敛到某个峰值点。 非有序数组的适用性 题目并没有要求数组有序。因为峰值是局部性质仅与相邻元素有关只需要每次确定搜索方向而不是依赖整体有序性。二分查找法的效率仍然得以保证。 举例说明
以数组 nums [1, 2, 1, 3, 5, 6, 4] 为例
初始 left 0, right 6取中间点 mid 3nums[mid] 3。比较 nums[mid] 和 nums[mid 1]3 5说明右侧有峰值更新 left mid 1。 第二轮 left 4, right 6取中间点 mid 5nums[mid] 6。比较 nums[mid] 和 nums[mid 1]6 4说明左侧有峰值更新 right mid。 第三轮 left 4, right 5取中间点 mid 4nums[mid] 5。比较 nums[mid] 和 nums[mid 1]5 6说明右侧有峰值更新 left mid 1。 最终 left right 5返回 5此时峰值为 6。 总结
二分查找法在这道题中能用是因为
峰值的定义是局部性质不依赖数组整体有序性。每次比较中点和其右侧元素可以有效缩小搜索范围。这种方法本质上是利用数组的递增和递减趋势来确定峰值位置。
