在 Go 中旋转数组

Question

这是一个 LeetCode 问题：189。旋转数组:

给定一个数组，将数组向右旋转 k 步，其中 k 是 非负数。

示例1：

输入：[1,2,3,4,5,6,7] 且 k = 3
输出：[5,6,7,1,2,3,4]

这是我的解决方案：

func rotate(nums []int, k int)  {
    k = k % len(nums)
    nums = append(nums[k:],nums[0:k]...)
    fmt.Println(nums)
}

这是一个简单的算法，但它不起作用。

我是 Go 新手。我认为

nums

是按值传递的，对

nums

的更改不会影响真正的

nums

。

我怎样才能做到这一点？

Answer 1

在 Go 中，所有参数都是按值传递的。

Go 切片在运行时由切片描述符表示：

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

如果更改函数中的任何切片描述符值，则通常通过返回更改的切片描述符来传达更改。

---

您的

rotate

函数会更改切片

num

指向底层数组的指针和切片容量的值，因此返回

num

。

例如，在我修复了你的

rotate

算法中的错误之后，

package main

import "fmt"

func rotate(nums []int, k int) []int {
    if k < 0 || len(nums) == 0 {
        return nums
    }

    fmt.Printf("nums %p array %p len %d cap %d slice %v\n", &nums, &nums[0], len(nums), cap(nums), nums)

    r := len(nums) - k%len(nums)
    nums = append(nums[r:], nums[:r]...)

    fmt.Printf("nums %p array %p len %d cap %d slice %v\n", &nums, &nums[0], len(nums), cap(nums), nums)

    return nums
}

func main() {
    nums := []int{1, 2, 3, 4, 5, 6, 7}

    fmt.Printf("nums %p array %p len %d cap %d slice %v\n", &nums, &nums[0], len(nums), cap(nums), nums)

    nums = rotate(nums, 3)

    fmt.Printf("nums %p array %p len %d cap %d slice %v\n", &nums, &nums[0], len(nums), cap(nums), nums)
}

输出：

nums 0xc00000a080 array 0xc00001a1c0 len 7 cap 7 slice [1 2 3 4 5 6 7]
nums 0xc00000a0c0 array 0xc00001a1c0 len 7 cap 7 slice [1 2 3 4 5 6 7]
nums 0xc00000a0c0 array 0xc00001a240 len 7 cap 8 slice [5 6 7 1 2 3 4]
nums 0xc00000a080 array 0xc00001a240 len 7 cap 8 slice [5 6 7 1 2 3 4]

参考：Go 博客：Go Slices：用法和内部结构

Answer 2

这么晚才回答，是因为我在阅读《Go 编程语言》一书时遇到了这个问题。它提出了一个非常优雅的算法来使用反向函数并应用它三次以实现所需的 k 元素旋转。像这样的东西

// function to rotate array by k elems (3 reverse method)
func rotate(arr []int, k int) {
    reverse(arr[:k])
    reverse(arr[k:])
    reverse(arr)
}

请注意，您必须编写一个反向函数。 Go 没有提供这一点。这是一个 O(n) 解决方案，占用 O(1) 空间。

Answer 3

这是我对相同黑客等级的解决方案问题

func rotateLeft(d int32, arr []int32) []int32 {
    for ; d > 0 ; d-- {
        left := arr[0]
        arr = arr[1:]
        arr = append(arr, left)        
    }
    return arr
}

Answer 4

这是一种旋转 float 32 切片的方法，您可以将其更改为其他类型。

//RotateF32Slice positive n rotate to the left, negative to right
func RotateF32Slice(slice []float32, n int) (rotateSlice []float32) {
    var begin []float32
    var end []float32
    size := len(slice)
    rotateSlice = make([]float32, size)

    nAbs := math.Abs(float64(n))

    if int(nAbs) > size {
        remainder, _ := QuotientAndRemainderF32(float32(n), float32(size))
        n = int(remainder)
    }

    if n != 0 {
        if n > 0 {
            index := size - n
            begin = slice[index:]
            end = slice[0:index]
            copy(rotateSlice, begin)
            copy(rotateSlice[n:], end)
        } else {
            n = int(nAbs)
            index := size - n
            begin = slice[n:]
            end = slice[0:n]
            copy(rotateSlice, begin)
            copy(rotateSlice[index:], end)
        }
    } else {
        copy(rotateSlice, slice)
    }

    return rotateSlice
}

//QuotientAndRemainderF32 Computes the integer quotient and the remainder of the inputs. This function rounds floor(x/y) to the nearest integer towards -inf.
func QuotientAndRemainderF32(x, y float32) (Remainder, Quotient float32) {
    Quotient = float32(math.Floor(float64(x / y)))
    Remainder = x - y*Quotient
    return Remainder, Quotient
}

Answer 5

解决方案

解决方案1：

func rotate(ar []int,d,n int) []int{
    var newArray []int
    for i:=0;i<d;i++{
        newArray = ar[1:n]
        newArray = append(newArray,ar[0])
        ar = newArray
    }

    return ar
}

解决方案2：

func rotateR(ar []int,d,n int) []int{
    ar = append(ar[d:n],ar[0:d]...)
    return  ar
}

Answer 6

func rotate(nums []int, k int) {
    k = k % len(nums)
    result := append(nums[len(nums)-k:], nums[:len(nums)-k]...)
    for i := 0; i < len(nums); i++ {
        nums[i] = result[i]
    }
}

Answer 7

对我来说，这适用于许多数组旋转，但不适用于数百个 nums[]。

func rotate(nums []int, k int)  {
    for count:=k; count>0; count--{
        if len(nums) >= 1 && len(nums) <= 10^5 {
            for i:=len(nums)-1; i>0; i--{
                nums[i], nums[i-1] = nums[i-1], nums[i]
            }
        }
    }
}

Answer 8

给定一个数组，将数组向右旋转 k 步，其中 k 是 非负数。

示例1：

输入：[1,2,3,4,5,6,7] 且 k = 3 输出：[5,6,7,1,2,3,4] 块引用

首先，对于 k=3，输出不应该是 [4,5,6,7,1,2,3] ？

对于大多数数组操作，向新创建的数组添加元素总是比更改源数组更简单。如果数组不是很大（占用 Gig 内存/数十亿个项目等），您可以使用一个函数，按照您需要的顺序将元素添加到新创建的数组中并返回新元素：

// GO 1.18
func rot[T any](slice []T, k int) (newSlice []T){
    l := len(slice)
    for i := range slice {
        newSlice = append(newSlice, slice[(k+i) % l])
    }
    return
}

fmt.Printf("Slice %v after rotation %v\n", []int{1,2,3,4,5,6,7}, rot[int]([]int{1,2,3,4,5,6,7}, 3))
//Slice [1 2 3 4 5 6 7] after rotation [4 5 6 7 1 2 3]

如果你坚持使用“切片”，代码如下所示：

func rotationBySlicing[T any](slice []T, k  int) (newSlice []T) {
    if len(slice) == 0 {
        return slice
    }
    return append(slice[(k%len(slice)):],slice[0:k%len(slice)]...)
}


fmt.Printf("Array %v after rotation %v\n", []string{}, rotationBySlicing[string]([]string{},1))
    fmt.Printf("Array %v after rotation %v\n", []string{"a"}, rotationBySlicing[string]([]string{"a"},1))
    fmt.Printf("Array %v after rotation %v\n", []string{"a","b"}, rotationBySlicing[string]([]string{"a","b"},1))
    fmt.Printf("Array %v after rotation %v\n", []string{"a","b","c"}, rotationBySlicing[string]([]string{"a","b","c"},1))
    fmt.Printf("Array %v after rotation %v\n", []string{"a", "b", "c", "d"}, rotationBySlicing[string]([]string{"a", "b", "c", "d"},1))
    fmt.Printf("Slice %v after rotation %v\n", []int{1,2,3,4,5,6,7}, rotationBySlicing[int]([]int{1,2,3,4,5,6,7}, 3))


Array [] after rotation []
Array [a] after rotation [a]
Array [a b] after rotation [b a]
Array [a b c] after rotation [b c a]
Array [a b c d] after rotation [b c d a]
Array [1 2 3 4 5 6 7] after rotation [4 5 6 7 1 2 3]

说明还说：

其中 k 是非负数

，为了完整性，代码应该处理 k 小于 0 的情况

Answer 9

就我而言，我更喜欢下面的算法，因为我想保持切片容量相同：

// Rotation by keeping the capacity same
func Rotate(nums []int, k int) {
    k %= len(nums)
    new_array := make([]int, len(nums))
    copy(new_array[:k], nums[len(nums)-k:])
    copy(new_array[k:], nums[:len(nums)-k])
    copy(nums, new_array)
}

另外，我在 Leet 代码中测试了它，看起来不错:)

您还可以在函数顶部添加一个条件，使其为负移位（旋转）做好准备，

再次完整代码：

func Rotate(nums []int, k int) {
    k %= len(nums)
    // Condition below is added.
    if k < 0 {
        k += len(nums)
    }
    new_array := make([]int, len(nums))
    copy(new_array[:k], nums[len(nums)-k:])
    copy(new_array[k:], nums[:len(nums)-k])
    copy(nums, new_array)
}

Answer 10

基于@peterSO的答案，但适用于负

k

值：

func rotate(nums []float64, k int) []float64 {
    if len(nums) == 0 {
        return nums
    }

    kAbs := int(math.Abs(float64(k)))

    r := len(nums) - kAbs%len(nums)
    if k > 0 {
        nums = append(nums[r:], nums[:r]...)
    } else {
        nums = append(nums[kAbs:r], nums[r:]...)
    }

    return nums
}

Answer 11

这不起作用，因为

[]byte

是一个切片，有点像“指向数组的指针”。正在做：

func f(v []T) {
  v = ... //
}

不会对调用者产生任何可观察到的影响。假设你的

append

方式是正确的（没有真正检查过）你可以这样做：

func rotate(nums []int, k int) {
    k = k % len(nums)
    temp := append(nums[k:], nums[0:k]...)
    copy(nums, temp) // this actually writes to where nums points to
}

func main() {
    nums := []int{1,2,3,4,5,6,7}
    rotate(nums ,3)
    fmt.Println(nums)
}