内容简介:已知一个长度为 n 的数组和一个正整数 k,并且最多只能使用一个用于 交换数组元素的附加空间单元,试设计算法得到原数组循环右移 k 次的 结果并分析算法的时间复杂度。根据三步反转法,实现时间复杂度为O(n),空间复杂度为O(1)过程:
试设计算法得到原数组循环右移 k 次的 结果并分析算法的时间复杂度。
1.问题描述
已知一个长度为 n 的数组和一个正整数 k,并且最多只能使用一个用于 交换数组元素的附加空间单元,试设计算法得到原数组循环右移 k 次的 结果并分析算法的时间复杂度。
2.解决思路
根据三步反转法,实现时间复杂度为O(n),空间复杂度为O(1)
过程:
- 1、将整体数组进行反转,原顺序1,2,3,4,5,6,7,8,9变为9,8,7,6,5,4,3,2,1
- 2、将前K-1个数进行反转,比如K=2,则结果为:8,9,7,6,5,4,3,2,1
- 3、将后K个数进行反转,结果:8,9,1,2,3,4,5,6,7
3.代码实现
golang code:
package main import "fmt" func Do(arr []int64, k int) { if k > len(arr) { fmt.Println("error,k is beyond array length") } // 三步反转法 Reverse(arr, 0, len(arr)-1) Reverse(arr, 0, k-1) Reverse(arr, k, len(arr)-1) } func Reverse(arr []int64, start, end int) { for start < end { arr[start], arr[end] = arr[end], arr[start] start++ end-- } } func main() { arr := []int64{1, 2, 3, 4, 5, 6, 7, 8, 9} Do(arr, 5) fmt.Println(arr) }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
产品经理面试宝典
[美] Gayle Laakmann McDowell、[美]Jackie Bavaro / 吴海星、陈少芸 / 人民邮电出版社 / 2015-3 / 59.00元
本书针对IT 行业产品经理,以面试为主线,首先介绍产品经理职责以及谷歌、微软等知名企业中产品经理的作用和要求;然后采访了几位知名企业的产品经理,介绍成为产品经理的基本素质;之后从简历准备、各公司面试要点到具体面试问题进行详细分析,这部分是本书的重点内容。读者对象包括IT 行业产品经理以及对如何做好产品有兴趣的人士。一起来看看 《产品经理面试宝典》 这本书的介绍吧!