大家好，今天给大家分享的是关于ACWing平台上的题目《788. 逆序对的数量》的题解。这个问题主要考察了如何高效地计算数组中逆序对的数量。在开始之前，让我们先了解一下什么是逆序对。
🔍 什么是逆序对？
简单来说，在一个数组中，如果存在两个下标 i 和 j 满足 i < j 且 A[i] > A[j]，那么 (i, j) 就是一个逆序对。例如，在数组 [3, 1, 4, 2] 中，(3, 1) 和 (4, 2) 都是逆序对。
🛠️ 解题思路：
- 一种直接的方法是使用双重循环遍历数组来计算逆序对数量，但这时间复杂度较高。
- 更高效的解决方案可以采用分治法（Divide and Conquer）或者归并排序的思想来解决。通过归并排序，我们可以在 O(n log n) 的时间内完成计算。
🛠️ 具体步骤：
1. 使用归并排序的思想，将数组分成两部分。
2. 分别计算左半部分和右半部分的逆序对数量。
3. 计算跨越左右两部分的逆序对数量。
4. 合并排序后的数组。
📚 代码实现：
```python
def merge_sort_and_count(nums, temp, left, right):
if left >= right:
return 0
mid = (left + right) // 2
count = merge_sort_and_count(nums, temp, left, mid) + \
merge_sort_and_count(nums, temp, mid + 1, right)
i, j, pos = left, mid + 1, left
while i <= mid and j <= right:
if nums[i] <= nums[j]:
temp[pos] = nums[i]
i += 1
count += (j - (mid + 1))
else:
temp[pos] = nums[j]
j += 1
pos += 1
for k in range(i, mid + 1):
temp[pos] = nums[k]
count += (j - (mid + 1))
pos += 1
for k in range(j, right + 1):
temp[pos] = nums[k]
pos += 1
nums[left:right+1] = temp[left:right+1]
return count
```
希望这篇题解对你有所帮助！如果你有任何疑问或建议，欢迎在评论区留言讨论。🚀
算法 ACWing 归并排序