Golang单次遍历实现数组旋转的方法探讨

Golang单次遍历实现数组旋转的方法探讨 我正在阅读 《Go 程序设计语言》，作者 Alan Donovan。在第四章中，我在练习 4.4 的某些代码上遇到了困难，该练习要求“编写一个单次遍历即可完成旋转操作的版本？” 我想在左旋转次数方面稍作修改来实现它。

package main
import(
  "fmt"
)

func rotate(s []int,shift int){
   first := s[:shift]
   copy(s,s[shift:])   // 这会改变 first 的值
   s[len(s)-shift]=first  // 这行不通 !!!
}

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

有人能帮我理解切片的概念吗？


更多关于Golang单次遍历实现数组旋转的方法探讨的实战教程也可以访问 https://www.itying.com/category-94-b0.html

7 回复

是的。在我的情况下，我没有得到预期的行为。

更多关于Golang单次遍历实现数组旋转的方法探讨的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


Yamil_Bracho:

结构

即使切片的长度没有改变，底层数组在操作后也保持不变。

Go Playground - The Go Programming Language

你能在这里解释一下吗？

我在文档中找到了一篇关于此行为的不错的博客文章：https://blog.golang.org/slices#TOC_4.

我知道 append 函数说明，如果长度不变，它会修改底层数组，但在你的 Playground 示例中，这似乎并未发生。

切片是指向特定结构的指针（https://blog.golang.org/slices-intro），因此 first 只是一个指向切片内容的指针。如果你修改它，first 的内容也会改变，因为它指向相同的地址。

所以你可以使用以下代码来实现你想要的功能：

func rotate(s []int, shift int) {
   slc3 := make([]int, 0)
   slc3 = append(slc3, s[shift:]...)
   slc3 = append(slc3, s[:shift]...)
   copy(s, slc3)
}

因为它指向相同的地址。 所以你可以使用这段代码来完成你想做的事情：

经过更多阅读后，我理解了切片的工作原理。因此，我也编写了我的旋转函数版本，其空间复杂度为 O(n)。

// space is O(n)
func rotate(s []int,shift int)[]int{
    var newdata []int
    first := s[:shift]
    newdata = append(newdata,s[shift:]...)
    newdata = append(newdata,first...)
    return newdata
}
func main(){
    data := []int{1,2,3,4,5,6}
    left_shift := 3
    fmt.Println(rotate(data,left_shift))  // 4 5 6 1 2 3
}

我一直在尝试用 O(1) 的空间复杂度实现相同的功能。这可能吗？

我提出了一种原地旋转的 O(1) 空间复杂度解决方案。

其基本思路是：当你将第一个元素向左移动 r 个位置时，保存被替换位置的值，然后继续将元素向左移动 r 个位置进行替换，直到替换回第一个元素为止。

接着，对第二个元素重复此操作，依此类推，直到处理完 r 个元素，此时数组中的所有值都已旋转完毕。这总共只需要 len(s) 次数组修改操作。

package main
import (
    "fmt"
)

func main() {
        s := []int{0, 1, 2, 3, 4, 5}
        fmt.Println(s) // "[0 1 2 3 4 5]"
        // 将 s 向左旋转两个位置。
        rotate(s, 2)
        fmt.Println(s) // "[2 3 4 5 0 1]"
}

// rotate 原地将切片 s 向左旋转 shift 个位置。
func rotate(s []int, shift int) {
        for i, v := range s[:shift] {
                for j := i + len(s) - shift; j >= 0; j -= shift {
                        s[j], v = v, s[j]
                        fmt.Printf("i=%d, j=%d, v=%d, s=%v\n", i, j, v, s)
                }
        }
}

输出：

[0 1 2 3 4 5]
i=0, j=4, v=4, s=[0 1 2 3 0 5]
i=0, j=2, v=2, s=[0 1 4 3 0 5]
i=0, j=0, v=0, s=[2 1 4 3 0 5]
i=1, j=5, v=5, s=[2 1 4 3 0 1]
i=1, j=3, v=3, s=[2 1 4 5 0 1]
i=1, j=1, v=1, s=[2 3 4 5 0 1]
[2 3 4 5 0 1]

要实现单次遍历完成数组旋转，关键在于理解切片底层数组的共享机制。以下是两种高效的单次遍历实现方法：

方法一：三次反转法（最优解）

func rotate(s []int, shift int) {
    n := len(s)
    shift %= n // 处理 shift 大于数组长度的情况
    
    // 反转前 shift 个元素
    reverse(s[:shift])
    // 反转剩余元素
    reverse(s[shift:])
    // 反转整个切片
    reverse(s)
}

func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

方法二：使用额外空间单次遍历

func rotate(s []int, shift int) {
    n := len(s)
    shift %= n
    
    // 创建临时切片保存需要移动的元素
    temp := make([]int, shift)
    copy(temp, s[:shift])
    
    // 单次遍历移动元素
    for i := 0; i < n-shift; i++ {
        s[i] = s[i+shift]
    }
    
    // 将临时切片中的元素放回末尾
    for i := 0; i < shift; i++ {
        s[n-shift+i] = temp[i]
    }
}

原代码问题分析

你的代码问题在于：

  1. first := s[:shift] 创建的是底层数组的引用，不是独立副本
  2. copy(s, s[shift:]) 会覆盖 first 引用的内存区域
  3. s[len(s)-shift] = first 语法错误，不能将切片赋值给整数元素

切片概念说明

// 切片是数组的视图，共享底层数组
data := []int{1,2,3,4,5,6}
slice1 := data[:3]  // [1,2,3]，与 data 共享底层数组
slice2 := data[3:]  // [4,5,6]，同样共享底层数组

// 修改 slice1 会影响 data
slice1[0] = 99
fmt.Println(data)  // [99,2,3,4,5,6]

推荐使用三次反转法，时间复杂度 O(n)，空间复杂度 O(1)，且只遍历数组一次（每个元素被访问两次）。

回到顶部