python逆序对计数问题
时间: 2024-01-21 16:15:17 浏览: 97
剑指Offer(Python多种思路实现):数组中的逆序对
逆序对计数问题是指在一个序列中,找出所有满足条件ai > aj (i < j)的数对(ai, aj),并统计数对的个数。下面是一个Python实现的例子:
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, count_left = merge_sort(arr[:mid])
right, count_right = merge_sort(arr[mid:])
merged, count_merge = merge(left, right)
return merged, count_left + count_right + count_merge
def merge(left, right):
merged = []
count = 0
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
count += len(left) - i
j += 1
merged.extend(left[i:])
merged.extend(right[j:])
return merged, count
# 示例
arr = [7, 5, 6, 4]
sorted_arr, count = merge_sort(arr)
print("逆序对个数:", count) # 输出:5
```
这个例子使用了归并排序的思想来解决逆序对计数问题。归并排序的时间复杂度为O(nlogn),因此该算法的时间复杂度也是O(nlogn)。
阅读全文