热门标签 | 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时必定会找到局部峰值

 

 

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


推荐阅读
  • selenium通过JS语法操作页面元素
    做过web测试的小伙伴们都知道,web元素现在很多是JS写的,那么既然是JS写的,可以通过JS语言去操作页面,来帮助我们操作一些selenium不能覆盖的功能。问题来了我们能否通过 ... [详细]
  • LoadRunner中的IP欺骗配置与实践
    为了确保服务器能够有效地区分不同的用户请求,避免多人使用同一IP地址造成的访问限制,可以通过配置IP欺骗来解决这一问题。本文将详细介绍IP欺骗的工作原理及其在LoadRunner中的具体配置步骤。 ... [详细]
  • 本文探讨了Java编程语言中常用的两个比较操作符==和equals方法的区别及其应用场景。通过具体示例分析,帮助开发者更好地理解和使用这两个概念,特别是在处理基本数据类型和引用数据类型的比较时。 ... [详细]
  • 本文详细介绍了如何使用Rufus工具制作一个兼容UEFI启动模式的Windows Server 2008 R2安装U盘,包括必要的软件和步骤。 ... [详细]
  • 本文介绍如何使用 Python 计算两个时间戳之间的时间差,并将其转换为毫秒。示例代码展示了如何通过 `time` 和 `datetime` 模块实现这一功能。 ... [详细]
  • 本文介绍了一个来自AIZU ONLINE JUDGE平台的问题,即清洁机器人2.0。该问题来源于某次编程竞赛,涉及复杂的算法逻辑与实现技巧。 ... [详细]
  • egg实现登录鉴权(七):权限管理
    权限管理包含三部分:访问页面的权限,操作功能的权限和获取数据权限。页面权限:登录用户所属角色的可访问页面的权限功能权限:登录用户所属角色的可访问页面的操作权限数据权限:登录用户所属 ... [详细]
  • 本文介绍了用户界面(User Interface, UI)的基本概念,以及在iOS应用程序中UIView及其子类的重要性和使用方式。文章详细探讨了UIView如何作为用户交互的核心组件,以及它与其他UI控件和业务逻辑的关系。 ... [详细]
  • 本文探讨了线性表中元素的删除方法,包括顺序表和链表的不同实现策略,以及这些策略在实际应用中的性能分析。 ... [详细]
  • 实现Win10与Linux服务器的SSH无密码登录
    本文介绍了如何在Windows 10环境下使用Git工具,通过配置SSH密钥对,实现与Linux服务器的无密码登录。主要步骤包括生成本地公钥、上传至服务器以及配置服务器端的信任关系。 ... [详细]
  • 本文由chszs撰写,详细介绍了Apache Mina框架的核心开发流程及自定义协议处理方法。文章涵盖从创建IoService实例到协议编解码的具体步骤,适合希望深入了解Mina框架应用的开发者。 ... [详细]
  • 本文提供了一个关于AC自动机(Aho-Corasick Algorithm)的详细解析与实现方法,特别针对P3796题目进行了深入探讨。文章不仅涵盖了AC自动机的基本概念,还重点讲解了如何通过构建失败指针(fail pointer)来提高字符串匹配效率。 ... [详细]
  • 本报告记录了嵌入式软件设计课程中的第二次实验,主要探讨了使用KEIL V5开发环境和ST固件库进行GPIO控制及按键响应编程的方法。通过实际操作,加深了对嵌入式系统硬件接口编程的理解。 ... [详细]
  • LeetCode 102 - 二叉树层次遍历详解
    本文详细解析了LeetCode第102题——二叉树的层次遍历问题,提供了C++语言的实现代码,并对算法的核心思想和具体步骤进行了深入讲解。 ... [详细]
  • JavaScript 中引号的多层嵌套使用技巧
    本文详细介绍了在 JavaScript 编程中如何处理引号的多级嵌套问题,包括双引号、单引号以及转义字符的正确使用方法。 ... [详细]
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社区 版权所有