leetcode 315 解题报告
15 Dec 2015
一道由逆序对引出的题，考查了对经典的归并排序算法的理解。
题目描述
Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
分析
题目要求每个数字右边比它小的数字的个数。初看有明显的暴力方法，每次扫描右边的数字，统计比它小的数字个数。时间复杂度是 \(O(n^2)\)。当然，这题出出来就不是用这个复杂度可以通过的，因此要优化。
想到一个数字与每个右边比它小的数字构成的都是一个逆序对，因此题目就转化成了如何求以每个数字开头的逆序对数。如果是求总的逆序对数，那么算法很简单了，用树状数组或归并排序统计都可以在 \(O(nlogn)\) 的复杂度内完成。想到这里，应该可以想到是要把求总的逆序对数的算法加以改造，统计出以每个数开头的逆序对数。
我选择使用归并排序的方法。在归并排序合并的过程中，i 指向左边的部分，j 指向右边的部分。i 指向的数字记为 [i]， j 指向的数字记为 [j]。当 [i] 小于等于 [j] 时，没有逆序对产生，i 指针向后移。当 [i] 大于 [j] 时，在新的排好序的序列中，[j] 要出现在 [i] 之间，因此对于 [i] 以及它后面的所有数字，与 [j] 均构成了一个逆序对（因为根据归并排序的规则，左边的部分是排好序的，[i] 大于 [j] 那么 i 后面的数字一定都大于 [j]）。
数据结构方面，一个长度为 n 的数组 result 表示结果，result[i] 表示原序列中下标为 i 的数字后出现的比它小的数字个数。一个 struct 作为排序的基本单元，其中 num 表示原数字，index 表示该数字在原序列中的下标。在归并排序合并的过程中，加入一个计数器 plus ，表示进行到 i 时已经与 [i] 产生逆序对的数的数量。这样每次把 [i] 加入排序后的数组时，result[[i].index] 的值就加上 plus。完整的一次归并排序后就完成了统计。
总结一下算法：
- 按输入序列顺序构造一个 struct 数组
counts，成员num为输入序列中数字的值，index为原序列下标。 - 构造一个数组
result作为结果，下标和原序列下标一一对应，值为原序列中该数字后比它小的数字的个数。 - 对
counts归并排序，在合并的过程中进行以下操作：- 令
i指向左边的数组，j指向右边的数组。计数器plus清零。 - 如果
[i]小于等于[j]，那么result[[i++].index] += plus。 - 如果
[i]大于[j]，那么plus++，j++。 - 重复上述过程直到左边或右边为空。
- 如果左边为空，则直接把右边剩余的部分全部加到结果序列中，本轮归并结束。
- 如果右边为空，
result[[i++].index] += plus直到左边为空，本轮归并结束。
- 令
- 此时
result数组即为所求。
心得
- 进入归并排序的函数时，要判断左边界是否小于右边界，不满足直接退出。不满足的情况有两种，一是左边界等于右边界，此时说明已经分到单个元素了；二是左边界大于右边界，这种情况会在输入序列为空的时候出现，因为进入的时候左右边界分别是 0 和
nums.size() - 1，如果输入序列为空，则左右边界值分别为 0 和 -1。 - 归并时的左中右划分。令
mid = (l + r) / 2，可不重不漏地把整个数组划分为[l, mid]和[mid + 1, r]两个部分。 - 归并时需要构造一个与当前区间相同大小的数组，用来存放本轮合并后的序列。在退出之前要把这段序列复制回原序列，然后销毁。