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

package main

import "fmt"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
func InversePairs(nums []int) int {
	// write code here
	divide(nums)
	return count
}

var count int = 0

func divide(nums []int) []int {
	if len(nums) <= 1 {
		return nums
	}
	mid := len(nums) / 2
	ll := divide(nums[0:mid])
	lr := divide(nums[mid:])
	return merge(ll, lr)
}
func merge(ll, lr []int) []int { //标准的合并方法
	dummy := []int{}
	lv, rv := 0, 0
	for lv < len(ll) && rv < len(lr) { //升序排列，之前卡了很久，不知道怎么处理不等长数列，原来是，lv，lr的进位可以保证前的的都是小数，则后面多的大数就可以自动接上去，不用排序。
		if ll[lv] <= lr[rv] {
			dummy = append(dummy, ll[lv])
			lv++
		} else {
			count += (len(ll) - lv) //第n位lr还大，n位为该数列最小值，那么n位后面的数都比lr大
            fmt.Println(count)
            count=count% 1000000007 //防止大数溢出，1^9+7，坑了我好久
			dummy = append(dummy, lr[rv])
			rv++
		}
	}
	for lv < len(ll) {
		dummy = append(dummy, ll[lv])
		lv++
	}
	for rv < len(lr) {
		dummy = append(dummy, lr[rv])
		rv++
	}
	return dummy
}