KK's blog

每天积累多一些

0%

LeetCode 493 Reverse Pairs

LeetCode 493 Reverse Pairs

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:

**Input:** nums = [1,3,2,3,1]
**Output:** 2

Example 2:

**Input:** nums = [2,4,3,5,1]
**Output:** 3

Constraints:

  • 1 <= nums.length <= 5 * 10<sup>4</sup>
  • -2<sup>31</sup> <= nums[i] <= 2<sup>31</sup> - 1

题目大意:

求数组的逆序数

解题思路:

  1. Merge sort模板
  2. merge分两部分写,一个部分比较求个数,另一部分排序

注意事项:

  1. merge分两部分写,一个部分比较,另一部分排序
  2. 计算个数由两部分组成,两指针部分和剩余元素部分。若以后半数组为主,就是前半数组指针i的后面个数(程序用此)
    若以前半数组为主(加入到res时候),就是后半数组指针j的前面个数
  3. 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
48
def 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)

Free mock interview