英文:
Golang: Passing in Slice as Reference issue
问题
我正在尝试编写一个程序来计算数组中的逆序对数量，但由于引用问题，我的数组没有被正确排序，这导致计数出错，尽管我认为在 Golang 中切片是按引用传递的。
以下是我的代码：
package main
import (
"fmt"
)
func InversionCount(a []int) int {
if len(a) <= 1 {
return 0
}
mid := len(a) / 2
left := a[:mid]
right := a[mid:]
leftCount := InversionCount(left) // 由于引用问题，没有被正确排序
rightCount := InversionCount(right) // 由于引用问题，没有被正确排序
res := make([]int, 0, len(right)+len(left)) // 临时切片，用于保存排序后的左侧和右侧
iCount := mergeCount(left, right, &res)
a = res // 将原始切片赋值为临时切片的值
fmt.Println(a) // 对于大多数情况，最终的 a 没有被正确排序
return iCount + leftCount + rightCount
}
func mergeCount(left, right []int, res *[]int) int {
count := 0
for len(left) > 0 || len(right) > 0 {
if len(left) == 0 {
*res = append(*res, right...)
break
}
if len(right) == 0 {
*res = append(*res, left...)
break
}
if left[0] <= right[0] {
*res = append(*res, left[0])
left = left[1:]
} else { // 发现逆序对
count += len(left)
*res = append(*res, right[0])
right = right[1:]
}
}
return count
}
func main() {
test := []int{4,2,3,1,5}
fmt.Print(InversionCount(test))
}
解决这个问题的最佳方法是使用归并排序算法来计算逆序对数量。在归并排序的过程中，可以通过在合并阶段计算逆序对的数量来解决这个问题。你已经实现了归并排序的一部分，但在合并过程中出现了引用问题，导致排序不正确。
为了解决这个问题，你可以修改 mergeCount 函数，使其返回合并后的切片，并将逆序对的数量作为额外的返回值。然后，在 InversionCount 函数中，将返回的合并后的切片重新赋值给 a，以确保排序正确。
这是修改后的代码：
package main
import (
"fmt"
)
func InversionCount(a []int) int {
if len(a) <= 1 {
return 0
}
mid := len(a) / 2
left := a[:mid]
right := a[mid:]
leftCount := InversionCount(left)
rightCount := InversionCount(right)
sorted, iCount := mergeCount(left, right)
copy(a, sorted) // 将排序后的切片复制回原始切片
fmt.Println(a)
return iCount + leftCount + rightCount
}
func mergeCount(left, right []int) ([]int, int) {
count := 0
res := make([]int, 0, len(right)+len(left))
for len(left) > 0 && len(right) > 0 {
if left[0] <= right[0] {
res = append(res, left[0])
left = left[1:]
} else {
count += len(left)
res = append(res, right[0])
right = right[1:]
}
}
res = append(res, left...)
res = append(res, right...)
return res, count
}
func main() {
test := []int{4,2,3,1,5}
fmt.Print(InversionCount(test))
}
这样修改后的代码应该能够正确计算数组中的逆序对数量，并且能够正确排序数组。
英文:
I'm trying to write a program that counts inversions within an array, but my array is not being sorted properly due to reference issues and thus messes up my count even though I thought slices were passed by reference in Golang.
Here is my code:
package main
import (
"fmt"
)
func InversionCount(a []int) int {
if len(a) <= 1 {
return 0
}
mid := len(a) / 2
left := a[:mid]
right := a[mid:]
leftCount := InversionCount(left) //not being sorted properly due to reference issues
rightCount := InversionCount(right) //not being sorted properly due to reference issues
res := make([]int, 0, len(right)+len(left)) //temp slice to hold the sorted left side and right side
iCount := mergeCount(left, right, &res)
a = res //assigns the original slice with the temp slice values
fmt.Println(a) //a in the end is not sorted properly for most cases
return iCount + leftCount + rightCount
}
func mergeCount(left, right []int, res *[]int) int {
count := 0
for len(left) > 0 || len(right) > 0 {
if len(left) == 0 {
*res = append(*res, right...)
break
}
if len(right) == 0 {
*res = append(*res, left...)
break
}
if left[0] <= right[0] {
*res = append(*res, left[0])
left = left[1:]
} else { //Inversion has been found
count += len(left)
*res = append(*res, right[0])
right = right[1:]
}
}
return count
}
func main() {
test := []int{4,2,3,1,5}
fmt.Print(InversionCount(test))
}
What would be the best possible way to solve this problem? I have tried to do something similar to what I did to the res array by forcing the mergeCountfunction to take in a reference of the array, but it seems very messy and it will give me errors.
答案1
得分: 11
你可以通过传递切片的指针来解决问题，像这样：
func InversionCount(a *[]int) int {
if len(*a) <= 1 {
return 0
}
mid := len(*a) / 2
left := (*a)[:mid]
right := (*a)[mid:]
leftCount := InversionCount(&left) // 由于引用问题，左侧未正确排序
rightCount := InversionCount(&right) // 由于引用问题，右侧未正确排序
res := make([]int, 0, len(right)+len(left)) // 临时切片，用于保存排序后的左侧和右侧
iCount := mergeCount(left, right, &res)
*a = res
fmt.Println(a) // 对于大多数情况，最终的 a 未正确排序
return iCount + leftCount + rightCount
}
或者使用 copy 并将 a = res 更改为 copy(a, res)。
英文:
You either have to pass a pointer to your slice like:
func InversionCount(a *[]int) int {
if len(*a) <= 1 {
return 0
}
mid := len(*a) / 2
left := (*a)[:mid]
right := (*a)[mid:]
leftCount := InversionCount(&left) //not being sorted properly due to reference issues
rightCount := InversionCount(&right) //not being sorted properly due to reference issues
res := make([]int, 0, len(right)+len(left)) //temp slice to hold the sorted left side and right side
iCount := mergeCount(left, right, &res)
*a = res
fmt.Println(a) //a in the end is not sorted properly for most cases
return iCount + leftCount + rightCount
}
Or use copy and change a = res to copy(a, res).
答案2
得分: 4
与其改变切片，我更倾向于让函数在合并步骤中返回获取的切片。
以下是以此形式编写的代码，包括一些类似单元测试的代码，用于将高效版本与朴素的O(N^2)计数进行比较。
package main
import "fmt"
// Inversions 返回排序后的输入以及找到的逆序对数量。
func Inversions(a []int) ([]int, int) {
if len(a) <= 1 {
return a, 0
}
left, lc := Inversions(a[:len(a)/2])
right, rc := Inversions(a[len(a)/2:])
merge, mc := mergeCount(left, right)
return merge, lc + rc + mc
}
func mergeCount(left, right []int) ([]int, int) {
res := make([]int, 0, len(left)+len(right))
n := 0
for len(left) > 0 && len(right) > 0 {
if left[0] >= right[0] {
res = append(res, left[0])
left = left[1:]
} else {
res = append(res, right[0])
right = right[1:]
n += len(left)
}
}
return append(append(res, left...), right...), n
}
func dumbInversions(a []int) int {
n := 0
for i := range a {
for j := i + 1; j < len(a); j++ {
if a[i] < a[j] {
n++
}
}
}
return n
}
func main() {
cases := [][]int{
{},
{1},
{1, 2, 3, 4, 5},
{2, 1, 3, 4, 5},
{5, 4, 3, 2, 1},
{2, 2, 1, 1, 3, 3, 4, 4, 1, 1},
}
for _, c := range cases {
want := dumbInversions(c)
_, got := Inversions(c)
if want != got {
fmt.Printf("Inversions(%v)=%d, want %d\n", c, got, want)
}
}
}
希望对你有所帮助！
英文:
Rather than mutate the slices, I'd just have the functions return the slices obtained during the merge step.
Here's code in that form, including some unit-test-like code which compares the efficient version with a naive O(N^2) count.
package main
import "fmt"
// Inversions returns the input sorted, and the number of inversions found.
func Inversions(a []int) ([]int, int) {
if len(a) <= 1 {
return a, 0
}
left, lc := Inversions(a[:len(a)/2])
right, rc := Inversions(a[len(a)/2:])
merge, mc := mergeCount(left, right)
return merge, lc + rc + mc
}
func mergeCount(left, right []int) ([]int, int) {
res := make([]int, 0, len(left)+len(right))
n := 0
for len(left) > 0 && len(right) > 0 {
if left[0] >= right[0] {
res = append(res, left[0])
left = left[1:]
} else {
res = append(res, right[0])
right = right[1:]
n += len(left)
}
}
return append(append(res, left...), right...), n
}
func dumbInversions(a []int) int {
n := 0
for i := range a {
for j := i + 1; j < len(a); j++ {
if a[i] < a[j] {
n++
}
}
}
return n
}
func main() {
cases := [][]int{
{},
{1},
{1, 2, 3, 4, 5},
{2, 1, 3, 4, 5},
{5, 4, 3, 2, 1},
{2, 2, 1, 1, 3, 3, 4, 4, 1, 1},
}
for _, c := range cases {
want := dumbInversions(c)
_, got := Inversions(c)
if want != got {
fmt.Printf("Inversions(%v)=%d, want %d\n", c, got, want)
}
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论