mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
82 lines
4.8 KiB
Markdown
82 lines
4.8 KiB
Markdown
# [493. Reverse Pairs](https://leetcode.com/problems/reverse-pairs/)
|
||
|
||
# 思路
|
||
|
||
求（重要）逆序对数。虽然求的不是普通的逆序对而是`i < j && nums[i] > 2*nums[j]`，但解法几乎都是一样的。我们甚至可以把逆序对定义成`i < j && nums[i] > f(nums[j])`。
|
||
|
||
## 思路一、归并排序
|
||
|
||
此题最经典的解法就是类似归并排序的分治法。即我们不断将大问题划分成两个子问题最后再合并起来，用式子表示就是`T(i, j) = T(i, m) + T(m+1, j) + C, m = (i+j)/2`。这里的C就是合并两个子问题，即“已知逆序对的两个数字分别位于子数组 nums[i, m] 和 nums[m+1, j] 之中，求满足这个条件的逆序对个数”。暴力求C的思路是用个两层循环遍历两个子数组，复杂度为平方级别，不可取。所以我们可以先对两个子数组排序，这样再用两个指针即可在线性复杂度内求得C。还需要解决最后一个问题，那就是如何对数组进行排序，我们当然可以直接调用STL中的`sort`，但是更快的方法是采用归并排序的思想里面的merge操作，因为不要忘了待排序数组的前后两半都是排好序的，这样我们每次排序的复杂度就是线性的。
|
||
|
||
关于merge操作，这里多少几句，STL中有两个相关函数：
|
||
1. `merge`: 将两个的有序的序列(两个序列可以在同一容器内)归并到另一个容器中；
|
||
* 例：`merge(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), vec3.begin())`
|
||
2. `inplace_merge`: 将一个容器内分两个有序的部分归并到本身的容器。
|
||
* 例：`inplace_merge(vec1.begin(), vec1.begin() + mid + 1, vec1.end(), cmp)`（第二个参数是后半部分的开始，即mid+1；另外可传入比较函数，默认`less<int>()`）
|
||
|
||
`inplace_merge`的基本思想就是开辟额外的空间，然后再归并到本身的容器里，我们也可以自己实现这个函数（亲测会快一些），见代码中的`my_merge`。
|
||
|
||
时间复杂度O(nlogn)，空间复杂度O(n)
|
||
|
||
## 思路二
|
||
|
||
根据用户`fun4LeetCode`在评论区的[帖子](https://leetcode.com/problems/reverse-pairs/discuss/97268/general-principles-behind-problems-similar-to-reverse-pairs)，除了思路一之外，还有另外一种思路。
|
||
|
||
根据这个帖子，作者说这类问题的**核心就是将大问题划分成小问题求解**，并总结了两个常用的划分方式：
|
||
1. Sequential recurrence relation：即`T(i, j) = T(i, j - 1) + C`，C代表最后一个元素与前面所有元素的合并。
|
||
2. Partition recurrence relation：即`T(i, j) = T(i, m) + T(m + 1, j) + C, m = (i+j)/2`，C代表前后两个部分的合并。
|
||
|
||
即思路一使用的就是`Partition recurrence relation`，其实还可以使用`Sequential recurrence relation`。
|
||
|
||
为了求得此时的C（求最后一个元素与其他元素之间构成的逆序对数），暴力的思路就是挨个比较最后一个元素与其他所有元素的大小关系，但更快的思路是使用插入和搜索都很快的数据结构，例如平衡二叉搜索树、线段数组（binary indexed tree）和线段树等，详情请参考[原贴](https://leetcode.com/problems/reverse-pairs/discuss/97268/general-principles-behind-problems-similar-to-reverse-pairs)。
|
||
|
||
> 这个帖子总结得非常好，先挖个坑，有空了再仔细学习学习。
|
||
|
||
# C++
|
||
## 思路一
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
vector<int>nums_bk = vector<int>(50000);
|
||
void my_merge(vector<int>& nums, int l, int mid, int r){
|
||
/*手动实现inplce_merge, 要求nums[l~mid]和nums[mid+1~r]是已有序的*/
|
||
if(l == r) return;
|
||
for(int i = l; i <= r; i++) nums_bk[i] = nums[i];
|
||
|
||
int i = l, j = mid + 1, idx = l;
|
||
while(i <= mid && j <= r){
|
||
if(nums_bk[i] <= nums_bk[j]) nums[idx++] = nums_bk[i++];
|
||
else nums[idx++] = nums_bk[j++];
|
||
}
|
||
while(i <= mid) nums[idx++] = nums_bk[i++];
|
||
while(j <= r) nums[idx++] = nums_bk[j++];
|
||
}
|
||
|
||
int mergeSort(vector<int>& nums, int l, int r){
|
||
if(l >= r) return 0;
|
||
|
||
// 1. divide
|
||
int mid = (l + r) / 2, i = l, j = mid + 1;
|
||
int res = mergeSort(nums, l, mid) + mergeSort(nums, mid + 1, r);
|
||
// 此时前后两半都是各自有序的
|
||
|
||
// 2. conquer
|
||
while(i <= mid && j <= r){
|
||
if(nums[i] <= (long long)nums[j] * 2) i++;
|
||
else{
|
||
res += (mid - i + 1);
|
||
j++;
|
||
}
|
||
}
|
||
// sort(nums.begin() + l, nums.begin() + r + 1); // 无脑排序也可以只是复杂度为O(nlogn)
|
||
my_merge(nums, l, mid, r); // O(n)
|
||
// inplace_merge(nums.begin() + l, nums.begin() + mid + 1, \
|
||
// nums.begin() + r + 1, less<int>()); // O(n)
|
||
return res;
|
||
}
|
||
public:
|
||
int reversePairs(vector<int>& nums) {
|
||
return mergeSort(nums, 0, nums.size() - 1);
|
||
}
|
||
};
|
||
``` |