【问题描述】找到一个数组中逆序对 【输入形式】13,8,10,6,15,18,12,20,9,14,17,19 【输出形式】20 【样例输入】13,8,10,6,15,18,12,20,9,14,17,19【样例输出】 【样例说明】20 【评分标准】 严格按照题目要求使用C++完成

### 使用 C++ 实现计算数组中逆序对的数量 #### 方法一：基于归并排序的实现 通过修改传统的归并排序算法，在合并两个有序子数组的过程中统计逆序对的数量。以下是完整的代码实现： ```cpp #include <iostream> using namespace std; void countAndMerge(int* arr, int l, int m, int r, int& num) { int n1 = m - l + 1; int n2 = r - m; // 创建临时数组 int L[n1 + 1], R[n2 + 1]; for (int i = 0; i < n1; ++i) L[i] = arr[l + i]; for (int j = 0; j < n2; ++j) R[j] = arr[m + 1 + j]; L[n1] = INT_MAX; R[n2] = INT_MAX; int i = 0, j = 0; for (int k = l; k <= r; ++k) { if (L[i] <= R[j]) { arr[k] = L[i++]; } else { arr[k] = R[j++]; num += (m + 1) - (l + i); // 统计逆序对数量 } } } void mergeSortAndCount(int* arr, int l, int r, int& num) { if (l < r) { int m = l + (r - l) / 2; mergeSortAndCount(arr, l, m, num); mergeSortAndCount(arr, m + 1, r, num); countAndMerge(arr, l, m, r, num); } } int calculateInversions(int* arr, int size) { int inversions = 0; mergeSortAndCount(arr, 0, size - 1, inversions); return inversions; } int main() { int arr[] = {2, 3, 8, 6, 1}; int size = sizeof(arr) / sizeof(arr[0]); int result = calculateInversions(arr, size); cout << "Number of Inversions: " << result << endl; return 0; } ``` 上述方法的时间复杂度为 \(O(n \log n)\)，空间复杂度为 \(O(n)\)[^1]。 --- #### 方法二：暴力法（适用于小型数据集） 对于较小的数据规模，可以直接使用双重循环逐一比较每一对元素，判断其是否构成逆序对。这种方法简单直观，但时间复杂度较高 (\(O(n^2)\))。 ```cpp #include <iostream> using namespace std; int bruteForceCalculateInversions(const int* arr, int size) { int inversions = 0; for (int i = 0; i < size - 1; ++i) { for (int j = i + 1; j < size; ++j) { if (arr[i] > arr[j]) { ++inversions; } } } return inversions; } int main() { int arr[] = {2, 3, 8, 6, 1}; int size = sizeof(arr) / sizeof(arr[0]); int result = bruteForceCalculateInversions(arr, size); cout << "Number of Inversions: " << result << endl; return 0; } ``` 此方法适合用于教学目的或验证其他高效算法的结果[^2]。 --- #### 方法三：树状数组优化 利用树状数组可以在 \(O(\log n)\) 时间内完成单次查询和更新操作，从而整体达到 \(O(n \log n)\) 的效率。以下是一个具体的实现方式： ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; long long BIT[MAXN]; // 获取最低有效位 inline int lowbit(int x) { return x & (-x); } // 更新树状数组 void updateBIT(int idx, int val, int maxVal) { while (idx <= maxVal) { BIT[idx] += val; idx += lowbit(idx); } } // 查询前缀和 long long queryBIT(int idx) { long long sum = 0; while (idx > 0) { sum += BIT[idx]; idx -= lowbit(idx); } return sum; } long long countInversionsUsingFenwickTree(vector<int>& nums) { vector<pair<int, int>> sortedNums; int n = nums.size(); for (int i = 0; i < n; ++i) { sortedNums.emplace_back(make_pair(nums[i], i)); } sort(sortedNums.begin(), sortedNums.end()); // 映射原始数值到离散化后的索引 unordered_map<int, int> rankMap; int rank = 0; for (auto &[val, _] : sortedNums) { if (!rankMap.count(val)) { rankMap[val] = ++rank; } } memset(BIT, 0, sizeof(BIT)); long long inversions = 0; for (int i = n - 1; i >= 0; --i) { int currentRank = rankMap[nums[i]]; inversions += queryBIT(currentRank - 1); updateBIT(currentRank, 1, rank); } return inversions; } int main() { vector<int> arr = {2, 3, 8, 6, 1}; long long result = countInversionsUsingFenwickTree(arr); cout << "Number of Inversions: " << result << endl; return 0; } ``` 该方法特别适合处理大规模输入场景下的逆序对统计问题[^3]。 --- #### 总结 以上三种方法分别针对不同需求提供了解决方案： - **归并排序** 是最常用的方法之一，兼具时间和空间上的平衡； - **暴力法** 虽然简单易懂，但在实际应用中受限于性能瓶颈； - **树状数组** 提供了一种高效的替代方案，尤其当面对超大数据量时表现出色。