题解 | #数组中的逆序对#

package main

import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * @param data int整型一维数组
 * @return int整型
 */
func InversePairs(data []int) int {
	// write code here
	if len(data) < 2 {
		return 0
	}
	count := 0 //记录个数
	var GuiBingSort func(l, r int)
	var GuiBing func(left, right, mid int)
	GuiBingSort = func(l, r int) {
		if l >= r {
			return
		}
		//分割成只有一个来比较
		mid := (l + r) / 2
		GuiBingSort(l, mid)
		GuiBingSort(mid+1, r)
		GuiBing(l, r, mid)
	}
	GuiBing = func(left, right, mid int) {
		//取出2个切片的第一个值的下标开始比较
		l, r := left, mid+1
		res := make([]int, right-left+1)
		index := 0 //是res的下标
		//左边切片长度到mid，mid是后面切片长度
		for l <= mid && r <= right {
			//左边比右边小直接放到切片里
			if data[l] <= data[r] {
				res[index] = data[l]
				l++
				index++
			} else { //右边比左边小需要计算逆序，加上左边切片剩余长度
				res[index] = data[r]
				r++
				index++
				//左边切片剩余长度
				count += mid + 1 - l
				count %= 1000000007
			}
		}
		//左切片、右切片剩余值放入res
		//即使左切片还有值也没有关系，因为比较右边的时候已经加上去了
		for l <= mid {
			res[index] = data[l]
			index++
			l++
		}
		for r <= right {
			res[index] = data[r]
			index++
			r++
		}
		l = left
		//整理好的放回原来位置
		for _, v := range res {
			data[l] = v
			l++
		}
	}
	GuiBingSort(0, len(data)-1)
	return count
}

func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7, 0}
	b := InversePairs(a)
	fmt.Println(b)
}