循环左移-海豚算法

2024-04-14 18:48
文章标签 算法 循环 左移 海豚

本文主要是介绍循环左移-海豚算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目要求是这样的:

 

/*

设将n (n > 1) 个整数存放到一维数组 R中。设计一个在时间和空间两方面尽可能高效的算法。

将 R 中的序列循环左移 p(0 < p < n)个位置,即将 R 中的数据由 (a0, a1, ……an-1)

变换为(ap, ap-1, …an-1, a0, a1, …, ap-1)。要求:

       (1) 给出算法的基本设计思想。

       (2) 根据设计思想,采用C或C++或JaVa语言描述算法,关键之处给出注释。

       (3) 说明你所设计算法的时间复杂度和空间复杂度。

*/

下面是我的一个低效实现:

只是稍微测试了下,查看参考答案后发现这个算法叫做海豚算法,下面是其给出的参考实现:

大致思路为:

 

首先把序列{ a0, a1, ..., ap, …, an-1 }逆转为{an-1, an-2, ..., ap, …,a0 },

再分别逆转{ an-1, an-2, ..., ap }和{ ap-1, ap-2, …,a0 },

最后得到{ ap, ap+1, …, an-1, a0, …, ap-1}。

 

我实现的那个空间复杂度比较高O(p),参考答案的为O(1),时间上面都是O(n)。

通过比较其他实现,发现自己在算法方面确实需要提高,我完全是按照那种常规思路来实现,没有进行任何优化,这在效率有要求的时候显然就不行了,这里还悟出一点道理,高效算法一般都不是大多数人想到的那种常规方法,即根据要求一步步满足,而应该根据算法输出结果来分析其中的规律进而找到突破点。

 

 

这篇关于循环左移-海豚算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/903723

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Python循环缓冲区的应用详解

《Python循环缓冲区的应用详解》循环缓冲区是一个线性缓冲区,逻辑上被视为一个循环的结构,本文主要为大家介绍了Python中循环缓冲区的相关应用,有兴趣的小伙伴可以了解一下... 目录什么是循环缓冲区循环缓冲区的结构python中的循环缓冲区实现运行循环缓冲区循环缓冲区的优势应用案例Python中的实现库

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

Java嵌套for循环优化方案分享

《Java嵌套for循环优化方案分享》介绍了Java中嵌套for循环的优化方法,包括减少循环次数、合并循环、使用更高效的数据结构、并行处理、预处理和缓存、算法优化、尽量减少对象创建以及本地变量优化,通... 目录Java 嵌套 for 循环优化方案1. 减少循环次数2. 合并循环3. 使用更高效的数据结构4

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for