If (a,b) in an array is in descending order, it is called an inversion pair. Returns the number of inversions.

Answer 2021-03-08:

1. Merge sort from right to left, equal copy to right. With the code. 2. Merge sort templates. With the code.

The code is written in Golang, and the code is as follows:

package main

import "fmt"

func main(a) {
    if true {
        arr := []int{3.1.7.0.2}
        ret := reverPairNumber1(arr)
        fmt.Println("1. From right to left, equal cuff to right:", ret)
    }
    if true {
        arr := []int{3.1.7.0.2}
        ret := reverPairNumber2(arr)
        fmt.Println("2. Merge sort template:, ret)
    }
}
func reverPairNumber1(arr []int) int {
    arrLen := len(arr)
    if arrLen <= 1 {
        return 0
    }
    return process1(arr, 0, arrLen- 1)}func process1(arr []int, L int, R int) int {
    curLen := R - L + 1
    if curLen <= 1 {
        return 0
    }

    / / point
    M := L + (R-L)>>1
    return process1(arr, L, M) + process1(arr, M+1, R) + merge1(arr, L, M, R)

}
func merge1(arr []int, L int, M int, R int) int {

    // Auxiliary array
    help := make([]int, R-L+1)
    i := R - L + 1 - 1
    p1 := M
    p2 := R
    res := 0
    // The same as the other
    for p1 >= L && p2 >= M+1 {
        if arr[p1] > arr[p2] {
            res += p2 - M
            help[i] = arr[p1]
            p1--
        } else {
            help[i] = arr[p2]
            p2--
        }
        i--
    }

    for p1 >= L {
        help[i] = arr[p1]
        p1--
        i--
    }
    for p2 >= M+1 {
        help[i] = arr[p2]
        p2--
        i--
    }

    // Copy the auxiliary array to the original array
    copy(arr[L:R+1], help)
    return res
}

func reverPairNumber2(arr []int) int {
    arrLen := len(arr)
    if arrLen <= 1 {
        return 0
    }
    return process2(arr, 0, arrLen- 1)}func process2(arr []int, L int, R int) int {
    curLen := R - L + 1
    if curLen <= 1 {
        return 0
    }

    / / point
    M := L + (R-L)>>1
    return process2(arr, L, M) + process2(arr, M+1, R) + merge2(arr, L, M, R)

}
func merge2(arr []int, L int, M int, R int) int {
    // Add new code
    ans := 0
    windowR := M + 1
    for i := L; i <= M; i++ {
        for windowR <= R && arr[i] > arr[windowR] {
            windowR++
        }
        ans += windowR - M - 1
    }

    // Auxiliary array
    help := make([]int, R-L+1)
    i := 0
    p1 := L
    p2 := M + 1
    // Who small copy who
    for p1 <= M && p2 <= R {
        if arr[p1] <= arr[p2] {
            help[i] = arr[p1]
            p1++
        } else {
            help[i] = arr[p2]
            p2++
        }
        i++
    }

    for p1 <= M {
        help[i] = arr[p1]
        p1++
        i++
    }
    for p2 <= R {
        help[i] = arr[p2]
        p2++
        i++
    }

    // Copy the auxiliary array to the original array
    copy(arr[L:R+1], help)
    return ans
}
Copy the code

The result is as follows:

Left god Java code sword refers to Offer 51. Array in reverse order to comment