当前位置: 首页 > news >正文

重庆江北网站建设淘宝seo软件

重庆江北网站建设,淘宝seo软件,自己做网站推广在那个网站,wordpress 文章添加子标题为了实现时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),可以使用二分查找法: 解题思路: 峰值的特性是:当前元素大于左右相邻元素。使用二分法: 如果 nums[mid] > nums[mid 1],说明峰值在左侧或当前…

在这里插入图片描述

为了实现时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn),可以使用二分查找法:

解题思路:

  1. 峰值的特性是:当前元素大于左右相邻元素。
  2. 使用二分法:
    • 如果 nums[mid] > nums[mid + 1],说明峰值在左侧或当前 mid 位置(包括 mid),因此将 right = mid
    • 否则峰值在右侧,因此将 left = mid + 1
  3. 不断收缩区间,直到 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;// 如果中点比右侧元素大,说明峰值在左侧(包括mid)if (nums[mid] > nums[mid + 1]) {right = mid;} else { // 否则峰值在右侧left = mid + 1;}}// 最终left和right会相遇,此时即为峰值位置return left;}
}

数组即便不是有序的,为什么仍然二分查找仍然可以找到峰值?

这是因为这道题的二分查找并不依赖于数组是否有序,而是利用了“峰值”的定义和数组的局部特性。

关键点

  1. 题目定义的峰值条件

    • 峰值是指某个元素严格大于其左右邻居的元素。
    • 如果一个元素 nums[mid] > nums[mid + 1],那么在 mid 或者其左侧一定存在一个峰值。
    • 如果 nums[mid] < nums[mid + 1],那么在 mid 的右侧一定存在一个峰值。
  2. 为什么可以二分?
    二分查找的核心在于:

    • 每次选择一个中间点 mid,并根据某个条件判断下一个搜索范围。
    • 在这道题中,“峰值”可以通过比较 nums[mid]nums[mid + 1] 来判断范围:
      • 如果 nums[mid] > nums[mid + 1]
        • 峰值在左侧或就是 mid,因为 mid 本身比右边的大(局部性质),可以舍弃右侧部分。
      • 如果 nums[mid] < nums[mid + 1]
        • 峰值一定在右侧,因为右边存在一个更大的值,最终会到达一个下降点形成峰值。

    这利用了“递增到下降”的局部特性来缩小搜索范围。

  3. 数学直观解释

    • 假设数组中不存在连续相等的数字(即没有平缓区域),并且在数组两端可以假想有值为负无穷的元素(题目已假设 nums[-1] = nums[n] = -∞)。
    • 在数组中总能找到一个峰值元素,原因是:
      • 如果数组中存在一个“上升”趋势,例如 nums[i] < nums[i+1],那么在右侧一定有一个峰值。
      • 如果数组中存在一个“下降”趋势,例如 nums[i] > nums[i+1],那么左侧也一定存在一个峰值。

    这种趋势保证了每次二分缩小范围后,最终一定会收敛到某个峰值点。

  4. 非有序数组的适用性
    题目并没有要求数组有序。因为峰值是局部性质(仅与相邻元素有关),只需要每次确定搜索方向,而不是依赖整体有序性。二分查找法的效率仍然得以保证。


举例说明

以数组 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

总结

二分查找法在这道题中能用,是因为:

  1. 峰值的定义是局部性质,不依赖数组整体有序性。
  2. 每次比较中点和其右侧元素,可以有效缩小搜索范围。
  3. 这种方法本质上是利用数组的递增和递减趋势来确定峰值位置。
http://www.ds6.com.cn/news/48052.html

相关文章:

  • 经常用表格进行页面布局seo服务建议
  • 网站设计布局怎么做ppt
  • 做网站那些好谷歌推广优化
  • 营销网站的优点制作网页app
  • 微网站建设云帆网络长春网站优化咨询
  • 企业模板免费下载优化大师官网
  • 衡阳市住房和城乡建设部网站营销策划方案ppt
  • 青岛即墨网站开发软文推广的标准类型
  • 深圳商城网站开发技术培训
  • 网页登录qq入口seo培训网
  • 中卫市网站开发制作b2b电子商务网站
  • 企业网站架构2022年7到8月份的十大新闻
  • 网站建设专业性网站建设的好公司
  • 手机网站建设设计网络营销产品概念
  • 福建省网站建设方案书最新网站推广方法
  • 我的世界做弊端网站网络营销的优势有哪些?
  • 宣传旅游网站建设的重点是什么百度seo排名360
  • 母婴类网站怎么建设全网搜索
  • 阿里云有了域名 网站建设百度提问登陆入口
  • 湖州市城乡建设局网站引流获客工具
  • 哔哩哔哩网站开发图片营销渠道有哪几种
  • 百度怎么做公司的网站优就业seo课程学多久
  • 网站建设确认单seo研究中心南宁线下
  • 一流本科专业建设点网站百度广告投放平台
  • 在线定制家具青岛谷歌优化
  • 肥乡网站建设企业如何网络推广
  • 南昌seo计费管理手机系统优化软件
  • 广州网站建设找哪里网站统计分析平台
  • 天河移动网站建设百度推广代理商
  • 二级网站收录seo的优化技巧和方法