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

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

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

}

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

查看所有标签

猜你喜欢:

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

内容创业:内容、分发、赢利新模式

内容创业:内容、分发、赢利新模式

张贵泉、张洵瑒 / 电子工业出版社 / 2018-6 / 49

越来越多的内容平台、行业巨头、资本纷纷加入内容分发的战争中,竞争非常激烈。优质的原创性内容将成为行业中最宝贵的资源。在这样的行业形势下,如何把内容创业做好?如何提高自身竞争力?如何在这场战争中武装自己?是每一位内容创业者都应该认真考虑的问题。 《内容创业:内容、分发、赢利新模式》旨在帮助内容创业者解决这些问题,为想要进入内容行业的创业者出谋划策,手把手教大家如何更好地进行内容创业,获得更高的......一起来看看 《内容创业:内容、分发、赢利新模式》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具

SHA 加密
SHA 加密

SHA 加密工具