试设计算法得到原数组循环右移 k 次的 结果并分析算法的时间复杂度。

小橙子Chelsea · · 381 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

试设计算法得到原数组循环右移 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)

}


有疑问加站长微信联系(非本文作者)

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

381 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传