刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。

示例 1:

输入：record = [9, 7, 5, 4, 6]
输出：8
解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。

限制：

• 0 <= record.length <= 50000

思路

这道题可能很多人第一反应就是双循环。思路完全正确，只可惜测试用例会让这种思路超时。。。

所以得换个新的思路：

• 既然 O(n^2) 不行，然后 O(n) 显然不现实，那就试试 O(n*logn)
• 从 O(n*logn) 这个复杂度，联想到了分治思想
• 尝试思考分治思想是否可行
  • 直接分块处理肯定不可以

  前后不同块的数据间还需要产生判断和计入结果，不可单独处理某块数据

  • 归并是否可行？

  前后两块数据之间的结果计算可行，单块数据内部的结果值可以递归处理，思路可行

• 具体归并思路
  • 递归深入，直到元素个数为零或者仅1个，这也就是递归的退出条件
  • 以升序数组为例，在归并进行中，两个指针分别指向前后两块的第一个元素，往后逐个遍历进行归并
  • 当发现左边元素比右边某个元素大时，那么就会有左边元素及其之后的所有元素都可以和右边当前元素形成一个逆序对，也就是可以计入结果了
  • 归并完成时，逆序对个数也就统计完毕了

思路差不多就是这样了，细节在注释~

代码

func reversePairs(record []int) int {
    // fail fast
	if len(record) <= 1 {
		return 0
	}

	var split func(i, j int) int
	split = func(start, end int) int {
        // 递归退出条件
		if start >= end {
			return 0
		}
		mid := (end-start)/2 + start
        // 收集深层的结果
		count := split(start, mid) + split(mid+1, end)
        // 暂存排序结果
		var temp []int
		i, j := start, mid+1
		for i <= mid && j <= end {
            // 结果是升序排列
            // 所以如果 左侧当前元素大于右侧当前元素，那么：
            // 左侧当前元素及其后续元素都能形成一个逆序对
			if record[i] > record[j] {
				count += mid - i + 1
				temp = append(temp, record[j])
				j++
			} else {
                // 右侧元素大无法形成逆序对，‘价值’榨干，抬走下一个
				temp = append(temp, record[i])
				i++
			}
		}
        // 剩余右侧元素时，说明比左侧元素大，无法形成逆序对
		for ; j <= end; j++ {
			temp = append(temp, record[j])
		}
        // 剩余左侧元素时，均能形成逆序对，但是之前计算时已经加过了，不用再加
		for ; i <= mid; i++ {
			temp = append(temp, record[i])
		}
        // 将这两段归并为升序数组，交给上层处理
		for z := start; z <= end; z++ {
			record[z] = temp[z-start]
		}
		return count
	}
	return split(0, len(record)-1)
}