Rotate Array in Go

问题:

This is a LeetCode problem: 189. Rotate Array:

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]

And here is my solution:

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

It is a straight forward algorithm but it does not work.

I am new to Go. I suppose nums is passed by value and changes to nums won't affect the real nums.

How can I get this right?

回答1:

In Go, all arguments are passed by value.

A Go slice is represented at runtime by a slice descriptor:

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

If you change any of the slice descriptor values in a function then communicate the change, typically by returning the changed slice descriptor.

---

Your rotate function changes the values of the slice num pointer to the underlying array and the slice capacity, so return num.

For example, after I fixed the bugs in your rotate algorithm,

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)
}

Output:

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]

Reference: The Go Blog: Go Slices: usage and internals

回答2:

Solutions

Solution 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
}

Solution 2 :

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

回答3:

This doesn't work because []byte is a slice which is sort of a "pointer to an array". Doing:

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

won't have any observable effect for the caller. Assuming your append way is correct (didn't really check it) you could do something like this:

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)
}