寻找数组中的峰值(极大值) |
您所在的位置：网站首页 › c语言求一个数组的最大值和最小值怎么求 › 寻找数组中的峰值(极大值) |
寻找数组中的峰值(极大值)
|
峰值元素是指其值大于左右相邻值的元素。 给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。 数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。 你可以假设 nums[-1] = nums[n] = -∞。 输入: nums = [1,2,3,1] 输出: 2 解释: 3 是峰值元素，你的函数应该返回其索引 2。 输入: nums = [1,2,1,3,5,6,4] 输出: 1 或 5 解释: 你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。 首先还是常规思路, 遍历一遍找出满足条件的值即可, 需要特殊处理下头部和尾部, 如果头部尾部已经满足条件了, 就不需要再遍历了, 直接返回即可. class Solution { func findPeakElement(_ nums: [Int]) -> Int { // 数组元素只有1个 if nums.count == 1 { return 0 } // 数组元素超过2个, 查看头部和尾部是否满足条件,如果满足可直接返回 // 查看头部是否满足条件 if nums[0]>nums[1] { return 0 } // 检查尾部是否满足条件 if nums.last! > nums[nums.count-2] { return nums.count-1 } // 从中间开始遍历查找 for i in 1..nums[i-1] && nums[i]>nums[i+1] { return i } } return -1 } }题目上有提示说可以做到O(logN)的时间复杂度, logN的时间复杂度自然就想到了2分查找.我们可以将 nums 数组中的任何给定序列视为交替的升序和降序序列。通过利用这一点，以及“可以返回任何一个峰作为结果”的要求，我们可以利用二分查找来找到所需的峰值元素。 在简单的二分查找中，我们处理的是一个有序数列，并通过在每一步减少搜索空间来找到所需要的数字。在本题中，我们需要对二分查找进行一点修改。首先从数组 nums中找到中间的元素 mid。若该元素恰好位于降序序列或者一个局部下降坡度中（当 nums[mid] > 右侧num[mid+1]时)，则说明峰值是自己或者在本元素的左边。于是，我们将搜索空间缩小为 [left , mid] (包括mid本身)。 若该元素恰好位于升序序列或者一个局部上升坡度中（当nums[mid] < num[mid+1] 时)，则说明峰值会在本元素的右边(mid肯定不会是峰值了,因为nums[mid] < num[mid+1] )。于是，我们将搜索空间缩小为 [mid+1, right] 的右边。 就这样循环下去，我们不断地缩小搜索空间，直到搜索空间中只有一个元素，该元素即为峰值元素。 class Solution { func findPeakElement(_ nums: [Int]) -> Int { var left = 0 var right = nums.count-1 while left < right { let mid = Int((left + right)/2) if nums[mid]>nums[mid+1] { right = mid } else { left = mid+1 } } return left } }
|
【本文地址】
今日新闻 |
推荐新闻 |