给定一个序列a1,a2,…,an,如果存在i < j并且ai > aj,那么我们称之为逆序对,求逆序对的数目 输入:第一行为n,表示序列长度,接下来的n行,第i+1行表示序列中的第i个数。 输出:所有逆序对总数
时间: 2023-12-03 20:45:36 浏览: 186
这道题可以使用归并排序的思想来解决。归并排序的过程中,将两个有序数组合并成一个有序数组时,如果左边数组的当前元素大于右边数组的当前元素,那么左边数组当前元素及其后面的所有元素都与右边数组当前元素构成逆序对。
因此,在归并排序的过程中,可以统计出当前左边数组中比右边数组当前元素大的元素的个数,即为逆序对的个数。最终的逆序对个数就是左半部分逆序对个数、右半部分逆序对个数和横跨两个部分的逆序对个数之和。
以下是 Python 代码实现:
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, num_left = merge_sort(arr[:mid])
right, num_right = merge_sort(arr[mid:])
merged, num_merged = merge(left, right)
return merged, num_left + num_right + num_merged
def merge(left, right):
i = j = 0
res = []
num = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
res.append(left[i])
i += 1
else:
res.append(right[j])
j += 1
num += len(left) - i
res += left[i:]
res += right[j:]
return res, num
n = int(input())
arr = []
for i in range(n):
arr.append(int(input()))
num = merge_sort(arr)[1]
print(num)
```
时间复杂度为 $O(n\log n)$,空间复杂度为 $O(n)$。
阅读全文