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

栏目: 编程工具 · 发布时间: 6年前

内容简介:已知一个长度为 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)

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Beginning ARKit for iPhone and iPad

Beginning ARKit for iPhone and iPad

Wallace Wang / Apress / 2018-11-5 / USD 39.99

Explore how to use ARKit to create iOS apps and learn the basics of augmented reality while diving into ARKit specific topics. This book reveals how augmented reality allows you to view the screen on ......一起来看看 《Beginning ARKit for iPhone and iPad》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具