这是一种合理、惯用的GoLang循环移位实现吗？

Question

有人可以评论一下，在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
    }
}

- ssh

---

对我来说，这看起来很好，用语也很地道。唯一我认为可以改进的是确保如果i大于len(a)，那么旋转的次数不要超过必要的范围。 - SirDarius

如果您不介意分配一个临时数组，长度为 i 元素，那么只需执行几个 copy() 操作可能更快。它能正确地处理重叠的源和目标。 - James Henstridge

Answer 1

逐个旋转切片并重复以获得期望的总旋转次数意味着需要花费与旋转距离 × 切片长度成正比的时间。但是，通过直接将每个元素移动到其最终位置，您可以在时间上仅与切片长度成正比的时间内完成此操作。

这段代码比您拥有的代码要棘手一些，并且您需要一个GCD函数来确定需要多少次遍历该切片：

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的切片向右旋转p个位置，等价于将其向左旋转l - p个位置，因此您可以使用rotateL来简化rotateR函数：

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

- matt

Answer 2

您的代码可以进行原地修改。

我不太明白您所说的按位操作的含义。也许这个链接能帮到您：

package main

    import "fmt"

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

    func rotateL(a *[]int, i int) {
        x, b := (*a)[:i], (*a)[i:]
        *a = append(b, x...)
    }

    func rotateR(a *[]int, i int) {
        x, b := (*a)[:(len(*a)-i)], (*a)[(len(*a)-i):]
        *a = append(b, x...)
    }

代码可以在https://play.golang.org/p/0VtiRFQVl7上运行。

在Go语言中，这被称为重新切片。在你的代码片段中，复制和循环是一种选择，而动态分配则是另一种选择。这取决于你，但是如果需要将10000个元素数组向右移动一个位置，则重新切片的成本要低得多。

- Uvelichitel

Answer 3

如果您需要输入多个值，任何您想要的（更新代码Uvelichitel）。

package main

import "fmt"

func main() {
    var N, n int
    fmt.Scan(&N)
    a := make([]int, N)
    for i := 0; i < N; i++ {
        fmt.Scan(&a[i])
    }
    fmt.Scan(&n)
    if n > 0 {
        rotateR(&a, n%len(a))
    } else {
        rotateL(&a, (n*-1)%len(a))
    }
    for _, elem := range a {
        fmt.Print(elem, " ")
    }
}

func rotateL(a *[]int, i int) {
    x, b := (*a)[:i], (*a)[i:]
    *a = append(b, x...)
}

func rotateR(a *[]int, i int) {
    x, b := (*a)[:(len(*a)-i)], (*a)[(len(*a)-i):]
    *a = append(b, x...)
}

- CompAces

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community

Answer 4

我喜欢Uvelichitel的解决方案，但如果您想要模数算术，那将是O(n)复杂度

package main
func main(){
   s := []string{"1", "2", "3"}
   rot := 5
   fmt.Println("Before RotL", s)
   fmt.Println("After RotL", rotL(rot, s))
   fmt.Println("Before RotR", s)
   fmt.Println("After RotR", rotR(rot,s))

}
func rotL(m int, arr []string) []string{
     newArr := make([]string, len(arr))

     for i, k := range arr{
         newPos := (((i - m) % len(arr)) + len(arr)) % len(arr)
         newArr[newPos] = k
     }

     return newArr
}

func rotR(m int, arr []string) []string{

     newArr := make([]string, len(arr))

     for i, k := range arr{
         newPos := (i + m) % len(arr)
         newArr[newPos] = k
      }
      return newArr
}

- Huy Tran