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
题目大意:
求数组的逆序数
解题思路:
- 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 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)
。