34、数组中的逆序对
题目描述:
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007。
解题思路:
分治思想,采用归并排序的思路来处理,如下图,先分后治:
先把数组分解成两个长度为2的子数组,再把这两个子数组分解成两个长度为1的子数组。接下来一边合并相邻的子数组,一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7>5,因此(7,5)组成一个逆序对。同样在第二对长度为1的子数组{6},{4}中也有逆序对(6,4),由于已经统计了这两对子数组内部的逆序对,因此需要把这两对子数组进行排序,避免在之后的统计过程中重复统计。
逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量。
Demo:
class Solution {
public:
int InversePairs(vector<int> data) {
vector<int> copy(data);
return InversePairsCore(data, copy, 0, data.size() - 1);
}
int InversePairsCore(vector<int> &data, vector<int> ©, int start, int end) {
if (start >= end) return 0;
int mid = start + (end - start) / 2;
// 交换copy数组和data数组,这样在遍历返回后因为copy数组的有序导致data的有序
int left = InversePairsCore(copy, data, start, mid);
int right = InversePairsCore(copy, data, mid + 1, end);
// i初始化为前半段最后一个数字的下标,j初始化为后半段最后一个数字的下标
int i = mid, j = end, indexcopy = end;
// 使用长整型不然通不过全部用例
long long int cnt = 0;
while (i >= start && j >= mid + 1) {
// 统计出相邻子数组之间的逆序对数目(data数组已经排好序了)
// 因为数组是有序的,如果data[i]>data[j],则data[j]以前的数据都小于data[i]
if (data[i] > data[j]) {
copy[indexcopy--] = data[i--];
cnt += (j - mid);
cnt %= 1000000007;
}
else {
copy[indexcopy--] = data[j--];
}
}
// 把剩余的数加入到辅助数组
for (; i >= start; --i)
copy[indexcopy--] = data[i];
for (; j >= mid + 1; --j)
copy[indexcopy--] = data[j];
return (left + right + cnt) % 1000000007;
}
};