剑指 Offer 51. 数组中的逆序对

 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

func reversePairs(nums []int) int {
    merge := func(l, mid, r int) int {
        tArr := make([]int, r-l+1)
        i, j, next, ret := l, mid+1, 0, 0
        for i <= mid && j <= r {
            // 注意：要使用 <= 而不是 <，使用小于会导致计算结果偏大。
            if nums[i] <= nums[j] {
                tArr[next] = nums[i]
                ret += j - mid - 1
                i++
            } else {
                tArr[next] = nums[j]
                j++
            }
            next++
        }
        for i <= mid {
            tArr[next] = nums[i]
            ret += r - mid
            i++
            next++
        }
        for j <= r {
            tArr[next] = nums[j]
            j++
            next++
        }
        for i := 0; i < len(tArr); i++ {
            nums[l+i] = tArr[i]
        }
        return ret
    }
    var count func(l, r int) int
    count = func(l, r int) int {
        if l >= r {
            return 0
        }
        mid := l + (r-l)/2
        left, right := count(l, mid), count(mid+1, r)
        return left + right + merge(l, mid, r)
    }
    return count(0, len(nums)-1)
}

 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

func reversePairs(nums []int) int {
    n := len(nums)
    tmp := make([]int, n)

    var mergeSort func([]int, []int, int, int) int
    mergeSort = func(nums, tmp []int, l, r int) int {
        if l >= r {
            return 0
        }

        mid := l + (r-l)/2
        leftPairs := mergeSort(nums, tmp, l, mid)
        rightPairs := mergeSort(nums, tmp, mid+1, r)
        if nums[mid] <= nums[mid+1] {
            return leftPairs + rightPairs
        }

        for i := l; i <= r; i++ {
            tmp[i] = nums[i]
        }

        i, j, count := l, mid+1, 0
        for k := l; k <= r; k++ {
            // 左半部分已经遍历完
            if i >= mid+1 {
                nums[k] = tmp[j]
                j++
            } else if j > r { // 右半部分已遍历完
                nums[k] = tmp[i]
                i++
            } else if tmp[i] <= tmp[j] {
                nums[k] = tmp[i]
                i++
            } else {
                nums[k] = tmp[j]
                count += mid + 1 - i
                j++
            }
        }

        return count + leftPairs + rightPairs
    }

    return mergeSort(nums, tmp, 0, n-1)
}

 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

var gNums []int

func reversePairs(nums []int) int {
    gNums = nums
    return mergeSort(0, len(nums)-1)
}

// mergeSort 排序 gNums 数组 [l...r] 区间的元素，注意：是左闭右闭区间
func mergeSort(l, r int) int {
    // 数组最多只有一个元素，逆序对数目为 0
    if l >= r {
        return 0
    }
    mid := l + (r-l)/2
    ans := mergeSort(l, mid) + mergeSort(mid+1, r)
    tArr, next, i, j := make([]int, r-l+1), 0, l, mid+1
    for i <= mid && j <= r {
        if gNums[i] <= gNums[j] {
            tArr[next] = gNums[i]
            ans += j - (mid + 1)
            i++
        } else {
            tArr[next] = gNums[j]
            j++
        }
        next++
    }
    for i <= mid {
        tArr[next] = gNums[i]
        ans += r - mid
        i++
        next++
    }
    for j <= r {
        tArr[next] = gNums[j]
        j++
        next++
    }
    for i, val := range tArr {
        gNums[l+i] = val
    }
    return ans
}