分治求排列的逆序数c++
时间: 2025-02-13 13:43:35 浏览: 75
### C++ 分治算法计算排列逆序数
为了高效地计算排列中的逆序数,可以采用基于归并排序的分治策略。这种方法不仅能够有效地找出所有的逆序对,而且还能保持较低的时间复杂度。
下面是一个完整的C++程序示例,展示了如何利用分治法来计算给定数组中的逆序数量:
```cpp
#include <vector>
using namespace std;
class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<int> tmp(nums.size());
return mergeSortCounting(nums, tmp, 0, nums.size() - 1);
}
private:
// 辅助函数用于执行实际的分割与合并操作,并统计逆序数
int mergeSortCounting(vector<int>& nums, vector<int>& tmp, int left, int right) {
if (left >= right) return 0;
int mid = left + (right - left) / 2;
int count = mergeSortCounting(nums, tmp, left, mid)[^4];
count += mergeSortCounting(nums, tmp, mid + 1, right);
count += mergeAndCountSplitInv(nums, tmp, left, mid, right);
return count;
}
// 合并两个子数组的同时计数跨越左右边界的逆序对数目
int mergeAndCountSplitInv(vector<int>& nums, vector<int>& tmp, int left, int mid, int right) {
for (int i = left; i <= right; ++i) tmp[i] = nums[i];
int i = left, j = mid + 1, k = left, inv_count = 0;
while (i <= mid && j <= right) {
if (tmp[i] <= tmp[j]) {
nums[k++] = tmp[i++];
} else {
nums[k++] = tmp[j++];
inv_count += (mid - i + 1); // 当右边元素小于左边时产生的全部逆序对
}
}
while (i <= mid) nums[k++] = tmp[i++];
while (j <= right) nums[k++] = tmp[j++];
return inv_count;
}
};
```
此代码实现了`reversePairs()`方法,该方法接收一个整型向量作为输入参数,并返回整个数组中存在的逆序对总数。内部逻辑遵循经典的归并排序框架,在每次合并过程中额外增加了逆序对的检测机制[^5]。
阅读全文
相关推荐


















