先把数组分割成子数组,统计出子数组内部逆序对的个数,再统计出两个相邻子数组之间逆序对的个数。
统计子数组内部逆序对的个数和相邻子数组逆序对的个数之后都要进行排序,以免在后续重复统计。
子数组内部直接排序,相邻子数组之间使用一个辅助数组,这个辅助数组是正序的,最后把辅助数组里的数存回原数组。
子数组内部:递归;
相邻子数组之间:两个指针i, j
,指向第一段的开头和第二段的开头,如果nums[i] <= nums[j]
,是正序对,所以直接把nums[i]
加入辅助数组,i
后移一位;如果nums[i] > nums[j]
,就会产生逆序对,因为num[i]
后面的数都比nums[i]
大,所以也会比nums[j]
大, 所以产生逆序对的数量为mid - i + 1
个,再把较小的数nums[j]
加入辅助数组中,j
后移一位。i
和 j
任意一个到达末尾会跳出循环,再把另一半还有剩余的加入到辅助数组。
是一个归并排序的模板,时间复杂度$O(nlogn)$
class Solution {
public:
int merge(vector<int>& nums, int l, int r) {
if (l >= r) return 0;
int mid = (l + r) >> 1;
// 分别计算左右两区间逆序对的个数
int res = merge(nums, l, mid) + merge(nums, mid + 1, r);
// 定义两个指针和临时数组
int i = l, j = mid + 1;
vector<int> temp;
while ( i <= mid && j <= r) {
if (nums[i] <= nums[j]) temp.push_back(nums[i ++ ]);
else {
temp.push_back(nums[j ++]);
res += mid - i + 1;
}
}
// 任意一边剩余的存入临时数组
while (i <= mid) temp.push_back(nums[i ++]);
while (j <= r) temp.push_back(nums[j ++]);
// 把临时数组的数存回原数组
i = l;
for (auto x : temp) nums[i ++] = x;
return res;
}
int inversePairs(vector<int>& nums) {
return merge(nums, 0, nums.size() - 1);
}
};