c++逆序对
时间: 2023-06-29 17:04:20 浏览: 69
逆序对是指在一个数列中,如果前面的数比后面的数大,则这两个数构成一个逆序对。例如,在数列 {2, 4, 1, 3, 5} 中,有三个逆序对:(2, 1), (4, 1), (4, 3)。
以下是一个使用归并排序求逆序对个数的 C++ 实现:
```c++
#include <iostream>
#include <vector>
using namespace std;
int merge(vector<int>& nums, int left, int mid, int right) {
int count = 0;
vector<int> temp(right - left + 1);
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
count += mid - i + 1;
}
}
while (i <= mid) temp[k++] = nums[i++];
while (j <= right) temp[k++] = nums[j++];
for (i = 0; i < k; i++) {
nums[left + i] = temp[i];
}
return count;
}
int mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return 0;
int mid = (left + right) / 2;
int count = mergeSort(nums, left, mid) + mergeSort(nums, mid + 1, right) + merge(nums, left, mid, right);
return count;
}
int reversePairs(vector<int>& nums) {
int n = nums.size();
if (n < 2) return 0;
return mergeSort(nums, 0, n - 1);
}
int main() {
vector<int> nums = {2, 4, 1, 3, 5};
int count = reversePairs(nums);
cout << count << endl; // 输出 3
return 0;
}
```
这个算法的时间复杂度是 O(nlogn),空间复杂度是 O(n)。