逆序对计数问题c++

逆序对计数问题是指在一个数组中，如果存在两个元素 a[i] 和 a[j]，且满足 i < j 且 a[i] > a[j]，则称这个组合 (a[i], a[j]) 为一个逆序对。解决这个问题的一种常见算法是使用归并排序。 下面是使用 C++ 实现逆序对计数问题的代码示例： ```cpp #include <iostream> #include <vector> using namespace std; long long merge(vector<int>& nums, int l, int mid, int r) { vector<int> temp(r - l + 1); int i = l, j = mid + 1; long long count = 0; for (int k = 0; k <= r - l; k++) { if (i > mid) { // 左半部分已经全部放入临时数组 temp[k] = nums[j++]; } else if (j > r) { // 右半部分已经全部放入临时数组 temp[k] = nums[i++]; } else if (nums[i] <= nums[j]) { // 左半部分当前元素小于等于右半部分当前元素 temp[k] = nums[i++]; } else { // 左半部分当前元素大于右半部分当前元素，构成逆序对 temp[k] = nums[j++]; count += mid - i + 1; // 统计逆序对个数 } } // 将临时数组的元素复制回原数组 for (int k = 0; k <= r - l; k++) { nums[l + k] = temp[k]; } return count; } long long mergeSort(vector<int>& nums, int l, int r) { if (l >= r) { return 0; // 当只有一个元素时，没有逆序对 } int mid = l + (r - l) / 2; long long count = 0; count += mergeSort(nums, l, mid); // 左半部分的逆序对个数 count += mergeSort(nums, mid + 1, r); // 右半部分的逆序对个数 count += merge(nums, l, mid, r); // 合并左右两部分，并统计逆序对个数 return count; } long long reversePairs(vector<int>& nums) { return mergeSort(nums, 0, nums.size() - 1); } int main() { vector<int> nums = {7, 5, 6, 4}; long long count = reversePairs(nums); cout << "逆序对个数：" << count << endl; return 0; } ``` 以上代码使用归并排序的思想，通过递归将数组分割成两半，然后再合并两个有序数组，并统计逆序对的个数。时间复杂度为 O(nlogn)，其中 n 是数组的长度。