go - 这是一个合理且惯用的 GoLang 循环移位实现吗？

Question

谁能评论这是否是一种合理且惯用的实现方式 circular shift Go 中的整数数组？ (我故意选择不使用位运算。)

如何改进？

package main

import "fmt"

func main() {
    a := []int{1,2,3,4,5,6,7,8,9,10}
    fmt.Println(a)
    rotateR(a, 5)
    fmt.Println(a)
    rotateL(a, 5)
    fmt.Println(a)
}

func rotateL(a []int, i int) {
    for count := 1; count <= i; count++ {
        tmp := a[0]
        for n := 1;n < len(a);n++ {
            a[n-1] = a[n]
        }
        a[len(a)-1] = tmp
    }
}

func rotateR(a []int, i int) {
    for count := 1; count <= i; count++ {
        tmp := a[len(a)-1]
        for n := len(a)-2;n >=0 ;n-- {
            a[n+1] = a[n]
        }
        a[0] = tmp
    }
}

Answer 1

一次旋转 slice 一个位置，并重复以获得所需的总旋转意味着它需要的时间与旋转距离 × slice 长度成正比。通过将每个元素直接移动到其最终位置，您可以在与 slice 长度成比例的时间内完成此操作。

The code for this比你做的要棘手一点，你需要一个 GCD 函数来确定遍历 slice 的次数:

func gcd(a, b int) int {
    for b != 0 {
        a, b = b, a % b
    }

    return a
}

func rotateL(a []int, i int) {

    // Ensure the shift amount is less than the length of the array,
    // and that it is positive.
    i = i % len(a)
    if i < 0 {
        i += len(a)
    }

    for c := 0; c < gcd(i, len(a)); c++ {

        t := a[c]

        j := c

        for {
            k := j + i
            // loop around if we go past the end of the slice
            if k >= len(a) {
                k -= len(a)
            }
            // end when we get to where we started
            if k == c {
                break
            }
            // move the element directly into its final position
            a[j] = a[k]
            j = k
        }

        a[j] = t
    }
}

将大小为 l 的 slice 向右旋转 p 个位置等同于将其向向左 旋转 l - p 个位置，因此您可以使用 rotateL 简化您的 rotateR 函数:

func rotateR(a []int, i int) {
    rotateL(a, len(a) - i)
}