阿里云 建网站攻略,做电子商务网站,网络推广的方法你知道几个?,协会网站建设必要性❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容#xff0c;和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣#xff01; 推荐#xff1a;数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航#xff1a; LeetCode解锁100… ❤️❤️❤️ 欢迎来到我的博客。希望您能在这里找到既有价值又有趣的内容和我一起探索、学习和成长。欢迎评论区畅所欲言、享受知识的乐趣 推荐数据分析螺丝钉的首页 格物致知 终身学习 期待您的关注 导航 LeetCode解锁1000题: 打怪升级之旅每题都包括3-5种算法以及详细的代码实现刷题面试跳槽必备漫画版算法详解通过漫画的形式和动态GIF图片把复杂的算法每一步进行详细可视解读看一遍就掌握python源码解读解读python的源代码与调用关系快速提升代码质量python数据分析可视化企业实战案例企业级数据分析案例与可视化提升数据分析思维和可视化能力程序员必备的数学知识与应用全面详细的介绍了工程师都必备的数学知识 期待与您一起探索技术、持续学习、一步步打怪升级 欢迎订阅本专栏❤️❤️ 在本篇文章中我们将详细解读力扣第162题“寻找峰值”。通过学习本篇文章读者将掌握如何使用多种方法来解决这一问题并了解相关的复杂度分析。每种方法都将配以详细的解释和ASCII图解以便于理解。
问题描述
力扣第162题“寻找峰值”描述如下 峰值元素是指其值大于左右相邻值的元素。给你一个输入数组 nums其中 nums[i] ≠ nums[i1]找到峰值元素并返回其索引。数组可能包含多个峰值在这种情况下返回任何一个峰值所在位置即可。你可以假设 nums[-1] nums[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。解题思路
初步分析 峰值元素是指其值大于左右相邻值的元素。可以使用线性扫描的方法找到峰值也可以使用二分查找来提高效率。
方法一线性扫描
步骤 遍历数组中的每个元素检查其是否大于左右相邻的元素。返回第一个满足条件的元素索引。
代码实现
def findPeakElement(nums):for i in range(len(nums)):if (i 0 or nums[i] nums[i - 1]) and (i len(nums) - 1 or nums[i] nums[i 1]):return ireturn -1# 测试案例
print(findPeakElement([1, 2, 3, 1])) # 输出: 2
print(findPeakElement([1, 2, 1, 3, 5, 6, 4])) # 输出: 1 或 5ASCII图解
假设输入数组为 [1, 2, 3, 1]图解如下
数组: [1, 2, 3, 1]遍历过程:
i 0, nums[i] 1 (不是峰值)
i 1, nums[i] 2 (不是峰值)
i 2, nums[i] 3 (是峰值)返回索引 2方法二二分查找
步骤 使用二分查找的方法在每次查找过程中比较中间元素与其相邻元素的大小。根据比较结果缩小查找范围直到找到峰值元素。
代码实现
def findPeakElement(nums):left, right 0, len(nums) - 1while left right:mid (left right) // 2if nums[mid] nums[mid 1]:right midelse:left mid 1return left# 测试案例
print(findPeakElement([1, 2, 3, 1])) # 输出: 2
print(findPeakElement([1, 2, 1, 3, 5, 6, 4])) # 输出: 1 或 5ASCII图解
假设输入数组为 [1, 2, 3, 1]图解如下
数组: [1, 2, 3, 1]初始状态: left 0, right 3第一次二分查找:
mid (0 3) // 2 1
nums[mid] 2, nums[mid 1] 3
nums[mid] nums[mid 1]
left mid 1 2第二次二分查找:
mid (2 3) // 2 2
nums[mid] 3, nums[mid 1] 1
nums[mid] nums[mid 1]
right mid 2最终状态: left 2, right 2返回索引 2复杂度分析
时间复杂度 线性扫描法O(n)其中 n 是数组的长度。二分查找法O(log n)其中 n 是数组的长度。 空间复杂度 两种方法均为 O(1)只使用了常数空间来存储计数变量和索引。
测试案例分析 测试案例 1 输入: nums [1, 2, 3, 1]输出: 2解释: 3 是峰值元素返回索引 2。 测试案例 2 输入: nums [1, 2, 1, 3, 5, 6, 4]输出: 1 或 5解释: 你的函数可以返回索引 1其峰值元素为 2或者返回索引 5其峰值元素为 6。
总结
本文详细解读了力扣第162题“寻找峰值”通过线性扫描法和二分查找法两种方法高效地解决了这一问题。希望读者通过本文的学习能够在力扣刷题的过程中更加得心应手。
参考资料
《算法导论》—— Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein力扣官方题解 如果觉得这篇文对你有帮助的话记得一键三连关注、赞、收藏是对作者最大的鼓励非常感谢 ❥(^_-) ❤️❤️关注公众号 数据分析螺丝钉 回复 学习资料 领取高价值免费学习资料❥(^_-)
