Golang中如何使用moves逻辑

Golang中如何使用moves逻辑 如何在Go语言中实现移动逻辑？例如：我有一个数组 = [1,2,3,4,5]，那么我如何创建一个函数，使得所有奇数移动到数组的开头，而偶数移动到数组的末尾，并且只移动一次或至少以最少的移动次数完成？

func main() {
    fmt.Println("hello world")
}
4 回复

我认为您正在寻找的算法是“分区”。我在Go Playground上写了一个简单的实现，看起来可以工作，但在没有进一步测试的情况下，我不会将其投入生产：

https://play.golang.org/p/bBXucwR_Npg

为了最小化移动次数，该分区算法是不稳定的。返回的枢轴索引将谓词评估为true的值与评估为false的值分隔开，例如：

ints := []int{1, 2, 3, 4, 5}
pivot := partitionInts(ints, func(i int) bool { return i&1 == 1 })
odds := ints[:pivot]
evens := ints[pivot:]

更多关于Golang中如何使用moves逻辑的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


这个链接对你有帮助吗：

package main

import (
	"fmt"
)

func main() {
	list := []int{1, 2, 3, 4, 5, 6}
	even := []int{}
	odd := []int{}
    sorted := []int{}

	for i := range list {
		if list[i]%2 == 0 {
			even = append(even, list[i])
		}
	}
	for i := range list {
		if list[i]%2 != 0 {
			odd = append(odd, list[i])
		}
	}

	sorted = append(odd, even...)
	fmt.Println(sorted)
}

如何创建一个函数，使得所有奇数都移动到数组的开头，偶数移动到末尾，并且移动次数最少？

一种移动次数最少、高效的实现：

package main

import "fmt"

func oddeven(a []int) {
	for i, j := 0, len(a)-1; i < j; i++ {
		if a[i]&1 == 0 {
			for ; i < j; j-- {
				if a[j]&1 != 0 {
					a[i], a[j] = a[j], a[i]
					break
				}
			}
		}
	}
}

func main() {
	a := []int{1, 2, 3, 4, 5, 0, -1, -2, -3, -4, -5}
	fmt.Println(a)
	oddeven(a)
	fmt.Println(a)
}

Go Playground - The Go Programming Language

[1 2 3 4 5 0 -1 -2 -3 -4 -5]
[1 -5 3 -3 5 -1 0 -2 4 -4 2]

在Go中实现移动逻辑可以使用双指针法，这是最高效的方式（O(n)时间复杂度，O(1)空间复杂度）。以下是实现代码：

package main

import "fmt"

func moveOddsToFront(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    
    left, right := 0, len(arr)-1
    
    for left < right {
        // 从左向右找第一个偶数
        for left < right && arr[left]%2 != 0 {
            left++
        }
        
        // 从右向左找第一个奇数
        for left < right && arr[right]%2 == 0 {
            right--
        }
        
        // 交换奇数和偶数
        if left < right {
            arr[left], arr[right] = arr[right], arr[left]
            left++
            right--
        }
    }
    
    return arr
}

func main() {
    // 示例1
    arr1 := []int{1, 2, 3, 4, 5}
    fmt.Println("原始数组:", arr1)
    fmt.Println("移动后:", moveOddsToFront(arr1))
    
    // 示例2
    arr2 := []int{2, 4, 6, 1, 3, 5}
    fmt.Println("\n原始数组:", arr2)
    fmt.Println("移动后:", moveOddsToFront(arr2))
    
    // 示例3
    arr3 := []int{1, 3, 5, 7, 9}
    fmt.Println("\n原始数组:", arr3)
    fmt.Println("移动后:", moveOddsToFront(arr3))
}

输出结果：

原始数组: [1 2 3 4 5]
移动后: [1 5 3 4 2]

原始数组: [2 4 6 1 3 5]
移动后: [5 3 1 6 4 2]

原始数组: [1 3 5 7 9]
移动后: [1 3 5 7 9]

如果需要保持奇数或偶数内部的相对顺序，可以使用以下稳定排序的方法：

func moveOddsToFrontStable(arr []int) []int {
    result := make([]int, len(arr))
    oddIndex, evenIndex := 0, len(arr)-1
    
    // 从后向前遍历，保持偶数顺序
    for i := len(arr) - 1; i >= 0; i-- {
        if arr[i]%2 == 0 {
            result[evenIndex] = arr[i]
            evenIndex--
        }
    }
    
    // 从前向后遍历，保持奇数顺序
    for i := 0; i < len(arr); i++ {
        if arr[i]%2 != 0 {
            result[oddIndex] = arr[i]
            oddIndex++
        }
    }
    
    return result
}

func main() {
    arr := []int{1, 2, 3, 4, 5, 6}
    fmt.Println("原始数组:", arr)
    fmt.Println("稳定移动后:", moveOddsToFrontStable(arr))
}

输出：

原始数组: [1 2 3 4 5 6]
稳定移动后: [1 3 5 2 4 6]

第一种方法使用双指针交换，移动次数最少（每个元素最多移动一次）。第二种方法保持相对顺序但需要额外空间。

回到顶部