剑指offer面试题51：数组中的逆序对（golang实现）

题目描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例1

输入: [7,5,6,4]
输出: 5

提示

0 <= 数组长度 <= 50000

算法分析

• 逆序数：在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。 一个排列中逆序的总数就称为这个排列的逆序数。由逆序数的定义可知，求解逆序数实际上就是求解一个数组能经过多少步原子操作变成一个有序数组，所以可以在排序的过程中统计逆序数。
• 为什么选择归并排序？

1. 归并排序是稳定的排序算法，即相同元素在排序前后顺序不变，这样才能准确统计逆序数。
2. 归并排序的时间复杂度为nlogn，冒泡排序同样能统计逆序数，但是50000的数据规模显然会超时。
3. 归并排序在合并区间的时候，能保证左右区间中的数据都是有序的，这使得统计逆序数变得很方便（在 right[j] 小于 left[i] 的时候，left[i] 右边的所有数都大于 right[j] ，所以逆序数可以直接加上 len(left) - i 。

复杂度分析

问题规模为数组的长度n

• 时间复杂度：O( n l o g n nlogn nlogn)，归并排序时间复杂度为nlogn。
• 空间复杂度：O( n n n)，left和right数组保存了原数组的内容。

Golang代码如下

func merge(left, right []int, count *int) []int {
	res := make([]int, len(left) + len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] > right[j] {
			res[i+j] = right[j]
			*count += len(left) - i
			j++
		} else {
			res[i+j] = left[i]
			i++
		}
	}
	for i < len(left) {
		res[i+j] = left[i]
		i++
	}
	for j < len(right) {
		res[i+j] = right[j]
		j++
	}
	return res
}

func mergeSort(nums []int, count *int) (res []int) {
	if len(nums) <= 1 {
		return nums
	}
	m := len(nums) / 2
	return merge(mergeSort(nums[:m], count), mergeSort(nums[m:], count), count)
}

func reversePairs(nums []int) (res int) {
	mergeSort(nums, &res)
	return
}