Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where 0 <= i < j < nums.length and nums[i] > 2 * nums[j].
Example 1:
<pre>Input: nums = [1,3,2,3,1] Output: 2 </pre>
Example 2:
<pre>Input: nums = [2,4,3,5,1] Output: 3 </pre>
Constraints:
1 <= nums.length <= 5 * 10<sup>4</sup>-2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1
题目大意：
求数组的逆序数
解题思路：
- Merge sort模板
- merge分两部分写，一个部分比较求个数，另一部分排序
注意事项：
- merge分两部分写，一个部分比较，另一部分排序
- 计算个数由两部分组成，两指针部分和剩余元素部分。若以后半数组为主，就是前半数组指针i的后面个数(程序用此)
若以前半数组为主(加入到res时候)，就是后半数组指针j的前面个数 - nums[start:end+1] = res，前面是nums不是res
Python代码：
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48def reversePairs(self, nums: List[int]):
if not nums:
return 0
return self.m_sort(nums, 0, len(nums) - 1)
def m_sort(self, nums, start, end):
if start >= end:
return 0
mid = start + (end - start) // 2
count = 0
count += self.m_sort(nums, start, mid)
count += self.m_sort(nums, mid + 1, end)
count += self.merge(nums, start, mid, end)
return count
def merge(self, nums, start, mid, end):
i, j, res, count = start, mid + 1, [], 0
while i <= mid and j <= end:
if nums[i] <= 2 * nums[j]:
i += 1
else:
count += mid - i + 1
j += 1
while i <= mid:
i += 1
while j <= end:
count += mid - i + 1
j += 1
i, j, res = start, mid + 1, []
while i <= mid and j <= end:
if nums[i] <= nums[j]:
res.append(nums[i])
i += 1
else:
res.append(nums[j])
j += 1
while i <= mid:
res.append(nums[i])
i += 1
while j <= end:
res.append(nums[j])
j += 1
nums[start:end + 1] = res
return count
算法分析：
时间复杂度为O(nlogn)，空间复杂度O(n)。
