热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

数据结构与算法(二):寻找峰值

一维:峰值规定:a[i]a[i-1]anda[i]a[i+1],假定只存在一个峰值121950例如9就是一个峰值方法一:顺序遍历,时间复杂度O(n)方法二:分治策略,将列表折半

一维:

峰值规定:a[i]>a[i-1] and a[i]>a[i+1],假定只存在一个峰值

1 2 1 9 5 0

 

 

例如9就是一个峰值

方法一:顺序遍历,时间复杂度O(n)

方法二:分治策略,将列表折半查找,第一次查找n/2,左右两边哪一边大继续折半查找哪一边

def search_peak(alist):
    l=0
    r=len(alist)-1
    while l<=r:
        mid=(l+r)//2
        if mid==0 or mid==len(alist)-1:
            return mid
        else:
            if alist[mid]]:
                r=mid-1
            elif alist[mid]]:
                l=mid+1
            else:
                return mid
    return -1
    
print(search_peak([1,1,1,1,1,2,3,5,7,9]))

这种写法并未考虑相邻两数相等情况的处理,并且只能处理查找一个峰值的情况,如果查找多个峰值,即使利用二分查找复杂度仍然会降为O(n)

时间复杂度分析:

1,首先进行一次折半得:T(n) = T(n/2) + O(1) 

2,n为剩余元素,O(1)代表进行一次比较

3,再次进行折半得:T(n) =  T(n/4) + O(1) *2

4,以此类推得:T(n) = T(n/2^k)+O(1)*k  #注意前面是幂,后面乘

5,令n/2^k=1(表示最后剩下一个元素)得:k=log2n

所以T(n) = O(1)*log2n = O(logn)

 

 二维:

  1  
2 5 3
  4  

 

 

 

 

长为m,宽为n

例如5就是一个峰值,通过算法找出来

方法一:贪婪上升算法,选择一个位置开始遍历,然后利用深度优先搜索一条路搜下去,最坏情况下时间复杂度是O(n*m)

方法二:分治策略:先二分求每一行的峰值,确定行峰值位置后,再判断它是不是大于列位置的相邻上下元素,时间复杂度为O(logn)

方法三:田字分割,时间复杂度O(n)

1,先找田字中最大的元素,此处为7

技术图片

2,找到后判断是否为峰值,若不是,记录相邻四点中最大值的坐标,继续分割最大值坐标所在象限

技术图片

 3,当范围缩小到3*3时必定会找到局部峰值

 

 

数据结构与算法(二):寻找峰值


推荐阅读
  • 题目探讨了在无向图中求解点连通数的问题,具体涉及UVA1660和POJ1966两个经典问题。通过最小割算法的应用,分析了如何高效地确定网络中的关键节点和路径,为电缆电视网络的优化设计提供了理论支持。该研究不仅验证了最小割算法的有效性,还为进一步探索复杂网络的连通性和鲁棒性奠定了基础。 ... [详细]
  • 本文深入解析了Java面向对象编程的核心概念及其应用,重点探讨了面向对象的三大特性:封装、继承和多态。封装确保了数据的安全性和代码的可维护性;继承支持代码的重用和扩展;多态则增强了程序的灵活性和可扩展性。通过具体示例,文章详细阐述了这些特性在实际开发中的应用和优势。 ... [详细]
  • 在探讨Hibernate框架的高级特性时,缓存机制和懒加载策略是提升数据操作效率的关键要素。缓存策略能够显著减少数据库访问次数,从而提高应用性能,特别是在处理频繁访问的数据时。Hibernate提供了多层次的缓存支持,包括一级缓存和二级缓存,以满足不同场景下的需求。懒加载策略则通过按需加载关联对象,进一步优化了资源利用和响应时间。本文将深入分析这些机制的实现原理及其最佳实践。 ... [详细]
  • 初探性能优化:入门指南与实践技巧
    在编程领域,常有“尚未精通编码便急于优化”的声音。为了从性能优化的角度提升代码质量,本文将带领读者初步探索性能优化的基本概念与实践技巧。即使程序看似运行良好,数据处理效率仍有待提高,通过系统学习性能优化,能够帮助开发者编写更加高效、稳定的代码。文章不仅介绍了性能优化的基础知识,还提供了实用的调优方法和工具,帮助读者在实际项目中应用这些技术。 ... [详细]
  • 如何高效利用Hackbar插件提升网页调试效率
    通过合理利用Hackbar插件,可以显著提升网页调试的效率。本文介绍了如何获取并使用未包含收费功能的2.1.3版本,以确保在不升级到最新2.2.2版本的情况下,依然能够高效进行网页调试。此外,文章还提供了详细的使用技巧和常见问题解决方案,帮助开发者更好地掌握这一工具。 ... [详细]
  • 并发编程入门:初探多任务处理技术
    并发编程入门:探索多任务处理技术并发编程是指在单个处理器上高效地管理多个任务的执行过程。其核心在于通过合理分配和协调任务,提高系统的整体性能。主要应用场景包括:1) 将复杂任务分解为多个子任务,并分配给不同的线程,实现并行处理;2) 通过同步机制确保线程间协调一致,避免资源竞争和数据不一致问题。此外,理解并发编程还涉及锁机制、线程池和异步编程等关键技术。 ... [详细]
  • ### 摘要`mkdir` 命令用于在指定位置创建新的目录。其基本格式为 `mkdir [选项] 目录名称`。通过该命令,用户可以在文件系统中创建一个或多个以指定名称命名的文件夹。执行此操作的用户需要具备相应的权限。此外,`mkdir` 还支持多种选项,如 `-p` 用于递归创建多级目录,确保路径中的所有层级都存在。掌握这些基本用法和选项,有助于提高在 Linux 系统中的文件管理效率。 ... [详细]
  • 在Android平台上,视频监控系统的优化与应用具有重要意义。尽管已有相关示例(如http:www.open-open.comlibviewopen1346400423609.html)展示了基本的监控功能实现,但若要提升系统的稳定性和性能,仍需进行深入研究和优化。本文探讨了如何通过改进算法、优化网络传输和增强用户界面来提高Android视频监控系统的整体效能,以满足更复杂的应用需求。 ... [详细]
  • POJ3669题目解析:基于广度优先搜索的详细解答
    POJ3669(http://poj.org/problem?id=3669)是一道典型的广度优先搜索(BFS)问题。由于陨石的降落具有时间属性,导致地图状态会随时间动态变化。因此,可以利用结构体来记录每个陨石的降落时间和位置,从而有效地进行状态更新和路径搜索。 ... [详细]
  • C# .NET 4.1 版本大型信息化系统集成平台中的主从表事务处理标准示例
    在C# .NET 4.1版本的大型信息化系统集成平台中,本文详细介绍了主从表事务处理的标准示例。通过确保所有操作要么全部成功,要么全部失败,实现主表和关联子表的同步插入。主表插入时会返回当前生成的主键,该主键随后用于子表插入时的关联。以下是一个示例代码片段,展示了如何在一个数据库事务中同时添加角色和相关用户。 ... [详细]
  • iOS 设备唯一标识获取的高效解决方案与实践
    在iOS 7中,苹果公司再次禁止了对MAC地址的访问,使得开发者无法直接获取设备的物理地址。为了在开发过程中实现设备的唯一标识,苹果推荐使用Keychain服务来存储和管理唯一的标识符。此外,还可以结合其他技术手段,如UUID和广告标识符(IDFA),以确保设备的唯一性和安全性。这些方法不仅能够满足应用的需求,还能保护用户的隐私。 ... [详细]
  • DRF框架中Serializer反序列化验证机制详解:深入探讨Validators的应用与优化
    在DRF框架的反序列化验证机制中,除了基本的字段类型和长度校验外,还常常需要进行更为复杂的条件限制校验。通过引入`validators`模块,可以实现自定义校验逻辑,如唯一字段校验等。本文将详细探讨`validators`的使用方法及其优化策略,帮助开发者更好地理解和应用这一重要功能。 ... [详细]
  • 本文探讨了如何有效地构建和优化微信公众平台账号,涵盖了用户信息管理、内容创作与发布、互动策略及数据分析等方面。通过合理设置用户信息字段,如用户名、昵称、密码、真实姓名和性别等,确保账号的安全性和用户体验。同时,文章还介绍了如何利用微信公众平台的各项功能,提升用户参与度和品牌影响力。 ... [详细]
  • 深入解析InnoDB中的多版本并发控制机制
    多版本并发控制(MVCC)是InnoDB存储引擎中的一项关键技术,通过维护数据在不同时间点的多个版本,确保了事务的隔离性和一致性。每个读取操作都能获得一个与事务启动时一致的数据视图,从而提高了并发性能并减少了锁竞争。此外,MVCC还支持多种隔离级别,如可重复读和读已提交,进一步增强了系统的灵活性和可靠性。 ... [详细]
  • 开发了一款Windows API查看器,支持VBA语句导出,并提供超过两万个API的MSDN链接查询功能。
    开发了一款名为Windows API Viewer的工具,支持导出VBA语句,并集成了超过两万个API的MSDN链接查询功能,方便用户快速查找和使用相关API信息。 ... [详细]
author-avatar
hanhan2502883243
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有