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

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param nums int整型一维数组
 * @return int整型
 */
//O(n)时间复杂度找开始变小的那个； O(logn)时间复杂度，递增有序序列。查找；找到目标值
//并归排序和二分查找很相似？
//O(n)空间复杂度 + O(nlogn)的时间复杂度； -> 并归排序 -> 递归? 循环？
//递归比循环好写
//
func InversePairs(nums []int) int {
	// write code here
	resCnt := 0
	mergeSort(nums, 0, len(nums)-1, &resCnt)
	return resCnt
}

// 并归+分治
// 这是并归排序的核心；合并两个有序数组; 并归排序的时候是数组本身内部进行变化；
func merge(nums []int, l, mid, r int, inverseCount *int) {
	tmpSorted := make([]int, r-l+1) //数组从l->r这个区间之间有序的部分
	si := 0                         //排序好部分的遍历下标
	i, j := l, mid+1
	for ; i <= mid && j <= r; si++ {
		if nums[i] < nums[j] {
			tmpSorted[si] = nums[i]
			i++
			continue
		}
		tmpSorted[si] = nums[j]
		j++
		*inverseCount += mid - i + 1 //重点：理解这个公式；第一个数组当中前i个元素是比当前元素小的，剩下的是比当前元素大的。大的元素和当前元素就会组成一个逆序对；因此mid-i+1个
		*inverseCount %= 1000000007
	}

	//剩余的部分都加回过去
	for i <= mid {
		tmpSorted[si] = nums[i]
		si++
		i++
	}
	for j <= r {
		tmpSorted[si] = nums[j]
		si++
		j++
	}
	for t, v := range tmpSorted {
		nums[l+t] = v
	}
}

// 递归+合并
func mergeSort(nums []int, l, r int, inverseCount *int) {
	mid := l + (r-l)/2
	//排序左边；数组本身上面进行排序
	if l < r {
		mergeSort(nums, l, mid, inverseCount)
		mergeSort(nums, mid+1, r, inverseCount)
		merge(nums, l, mid, r, inverseCount)
	}
}