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代码：

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)。