我正在尝试编写一个对数组内的反转进行计数的程序，但是由于引用问题，我的数组未正确排序，因此即使我认为切片是通过Golang中的引用传递的，也弄乱了我的计数。

这是我的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
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))
}

解决此问题的最佳方法是什么？ 我试图通过强制mergeCount函数接受数组的引用来执行与对res数组所做的操作类似的操作，但是它看起来非常混乱，并且会给我错误。

您要么必须将指针传递给切片，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
}

playground

或使用copy并将a = res更改为copy(a, res)。

playground

  • @DavidTrinh记得要投票并标记对您有帮助的答案。
  • @ dtrinh100您可以将其标记为已接受的答案。

除了改变切片之外，我只需要函数返回在合并步骤中获得的切片。

这是这种形式的代码，包括一些类似于单元测试的代码，该代码将有效版本与原始O(N ^ 2)计数进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
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
", c, got, want)
        }
    }
}