算法进阶——数组中的逆序对

题目

---

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围：对于 50% 的数据, size≤10⁴
对于 100% 的数据, size≤10⁵
数组中所有数字的值满足 0≤val≤10⁹

要求：空间复杂度O(n)，时间复杂度O(nlogn)

输入描述：
题目保证输入的数组中没有的相同的数字

示例1

输入：
[1,2,3,4,5,6,7,0]
返回值：
7

示例2

输入：
[1,2,3]
返回值：
0

思路

---

这题可以用归并统计法，也就是在归并排序的同时进行统计。

先了解归并排序算法，主要思想是先分后并：

• 将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止。
• 从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组。

归并统计法，关键点在于合并环节，在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。

举个例子：
在合并 {4 ,5} {1 , 2} 的时候，首先我们判断 1 < 4，我们即可统计出逆序对为2，为什么呢？这利用了数组的部分有序性。因为我们知道 {4 ,5} 这个数组必然是有序的，因为是合并上来的。此时当 1比4小的时候，证明4以后的数也都比1大，此时就构成了从4开始到 {4,5}这个数组结束，这么多个逆序对（2个），此时利用一个临时数组，将1存放起来，接着比较2和4的大小，同样可以得到有2个逆序对，于是将2也放进临时数组中，此时右边数组已经完全没有元素了，则将左边剩余的元素全部放进临时元素中，最后将临时数组中的元素放进原数组对应的位置。

可以看到下面这张图:

解答代码

---

class Solution {
public:/*** @param nums int整型vector * @return int整型*/int InversePairs(vector<int>& nums) {// write code hereint res = 0;vector<int> tmp(nums.size());MergeSort(nums, tmp, 0, nums.size() - 1, res);return res;}void MergeSort(vector<int>& nums, vector<int>& tmp, int left, int right, int& res) {// 递归结束if (left >= right) {return;}// 中心点int mid = left + (right - left) / 2;// 归并MergeSort(nums, tmp, left, mid, res);MergeSort(nums, tmp, mid + 1, right, res);Merge(nums, tmp, left, mid, right, res);}void Merge(vector<int>& nums, vector<int>& tmp, int left, int mid, int right, int& res) {int i = left; // 左子数组下标起点int j = mid + 1; // 右子数组下标起点int k = 0; //临时数组的下标起点while (i <= mid && j <= right) {if (nums[i] < nums[j]) {// 左子数组元素当前元素较小，无逆序，只进行排序tmp[k++] = nums[i++];} else {// 左子数组元素当前元素较大，排序同时记录逆序数tmp[k++] = nums[j++];res += mid + 1 - i;res %= 1000000007; // 应题目要求}}// 子数组中剩下元素全部存入临时数组while (i <= mid) {tmp[k++] = nums[i++];}while (j <= right) {tmp[k++] = nums[j++];}// 完成排序for (int i = left, j = 0; i <= right; i++, j++) {nums[i] = tmp[j];}}
};