题目来源于 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
问题
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
如：
输入: [7,5,6,4] 输出: 5
解法
暴力查找
暴力法，空间复杂度低，\(O(1)\)，时间复杂度太高！\(O({n^2})\)，
方法：
1
2
3
4
5
6
7
def reverse_pairs(nums: list) -> int:
num = 0
for i in range(len(nums) - 1):
for j in range(i + 1, len(nums)):
if nums[i] > nums[j]:
num += 1
return num
二分插入
二分插入排序，前面有多少个比它大的，当前数就有多少个逆序对，所有的加起来就是总的逆序对数量。时间复杂度 \(O(nlogn)\)，空间复杂度 \(O(n)\)。
1
2
3
4
5
6
7
8
9
10
11
12
def reverse_pairs(nums: list) -> int:
# 顺序的数组
q = []
# 逆序对的数量
res = 0
for v in nums:
# 不会修改q
i = bisect.bisect_left(q, -v)
res += i
# 修改q
q[i:i] = [-v]
return res
其中 bisect.bisect_left 的用法为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def bisect_left(a, x, lo=0, hi=None):
"""Return the index where to insert item x in list a, assuming a is sorted.
The return value i is such that all e in a[:i] have e < x, and all e in
a[i:] have e >= x. So if x already appears in the list, a.insert(x) will
insert just before the leftmost x already there.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
return lo
归并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution:
def reversePairs(self, nums: List[int]) -> int:
self.cnt = 0
def merge(nums, start, mid, end, temp):
i, j = start, mid + 1
while i <= mid and j <= end:
if nums[i] <= nums[j]:
temp.append(nums[i])
i += 1
else:
self.cnt += mid - i + 1
temp.append(nums[j])
j += 1
while i <= mid:
temp.append(nums[i])
i += 1
while j <= end:
temp.append(nums[j])
j += 1
for i in range(len(temp)):
nums[start + i] = temp[i]
temp.clear()
def mergeSort(nums, start, end, temp):
if start >= end: return
mid = (start + end) >> 1
mergeSort(nums, start, mid, temp)
mergeSort(nums, mid + 1, end, temp)
merge(nums, start, mid, end, temp)
mergeSort(nums, 0, len(nums) - 1, [])
return self.cnt