题目
Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].
You need to return the number of important reverse pairs in the given array.
Example1:
Input: [1,3,2,3,1]
Output: 2
Example2:
Input: [2,4,3,5,1]
Output: 3
Note:
The length of the given array will not exceed 50,000.
All the numbers in the input array are in the range of 32-bit integer.
给出一整数数组nums，找出符合 i<j ，同时 nums[i] > 2*nums[j]的数对个数：
- 数组长度不会超过 50000
- 所有整数都在 32 位整数范围内
解题思路
本题的条件有两个：
- i < j
- nums[i] > num[j] * 2
可以用分治法，将一个大问题化成若干个小问题：
- mergesort_and_count 中将 nums 从 mid 划分为两段数组，进行并归调用 mergesort_and_count 计算结果
- mergesort_and_count 中逐一比对 mid 左右两段的数字，找到符合 nums[i] > num[j] * 2 的数对，加值 count 后返回
- 分治时，若是暴力比对，则需要将 mid 右侧的所有数字都进行比对
- 若是在比对前左右就是有序数组的话，就可以比较到不符数对后即可返回，节省了比对的时间
- 所以这里就可以引出分治排序法中的并归排序（merge sort）了，在进行分治时，同时进行排序和比对操作
- 在分支到最深处，其实就是两个元素的数组，比对完之后，用 merge sort 进行排序，这样在下次比对时，mid 左右两侧就是有序数组了
代码实现
Runtime: 968 ms
Memory Usage: 21.6 MB
func reversePairs(_ nums: [Int]) -> Int {
//转化为可变数组
var numArr = nums
//通过 mergesort_and_count 进行排序和计算结果
return self.mergesort_and_count(&numArr, start: 0, end: nums.count - 1);
}
//计算 nums 中 start ... end 范围内的元素中符合 i<j && nums[i] > nums[j] * 2 的数对个数
//同时进行 mergesort 排序
func mergesort_and_count(_ nums: inout [Int], start: Int, end: Int)->Int{
//如果 start < end 才进行操作，否则返回符合条件数对个数为 0
if (start < end) {
//从中拆分 nums ，递归
let mid = (start + end) / 2;
var j = mid + 1;
// count 记录符合条件数对个数
var count = self.mergesort_and_count(&nums, start: start, end: mid) + self.mergesort_and_count(&nums, start: j, end: end);
//遍历寻找 start <= i <= mid < j <= end 中，nums[i] > nums[j] * 2 的数对个数，并加到 count
//由于 mid 左右两边都进行了升序排序，所以 j 找到第一个不符合 nums[i] > nums[j] * 2 后即可退出 while 循环，因为在后面都是更大的数，一定会不符合
for i in start ... mid {
while (j <= end && nums[i] > nums[j] * 2) {
j += 1
}
count += j - (mid + 1);
}
//mergesort排序
self.merge(&nums, start: start, mid: mid, end: end);
//返回结果
return count;
}else{return 0;}
}
func merge(_ nums: inout [Int], start: Int, mid: Int, end: Int)->Void
{
//将数组从 mid 拆分成两个子数组，逐一比对，返回较小者
let n1 = (mid - start + 1);
let n2 = (end - mid);
var L = [Int]();
var R = [Int]();
for i in 0 ..< n1{
L.append(nums[start + i])
}
for j in 0 ..< n2{
R.append(nums[mid + 1 + j])
}
var i = 0
var j = 0
for k in start ... end {
if (j >= n2 || (i < n1 && L[i] <= R[j])){
nums[k] = L[i];
i+=1
}else{
nums[k] = R[j];
j+=1
}
}
}
