剑指offer-51 数组中的逆序对(备忘)
强烈推荐这篇leetcode题解:
字节题库 - #剑51 - 困难 - 数组中的逆序对
这道题虽然是困难难度,但其实如果完全掌握了归并排序的思想,只需在归并排序
的模板上稍作修改就可以AC。可见算法基础还是太重要了。基础不牢,地动山摇。
简要说一下思路:分治的思想。
1.每次递归将序列对半划分为两个区间;
2.首先获得左侧区间的逆序对数量left,再获得右侧区间的逆序对数量right;
3.求两个区间之间的逆序对数量sum
4.返回left + right + sum;
难点其实就在于步骤3,在这一步需要在归并排序的基础上记录逆序对的数量。
其实如果完全掌握了归并排序的策略这道题一点都不难..我认为甚至还不如剑指
offer上的大多数中等难度的题。
代码如下,但是C++的代码强烈建议看上面链接中大佬的写法,详细注释。
初见写法(超时)
class Solution {
public:
int reversePairs(vector<int>& nums) {
if(nums.size() < 2) return 0;
return reverseP(nums, 0, nums.size() - 1);
}
int reverseP(vector<int>& nums, int l, int r){
if(l >= r)return 0;
int mid = (l + r) / 2;
int left = reverseP(nums, l, mid);
int right = reverseP(nums, mid + 1, r);
quickSort(nums, l, mid), quickSort(nums, mid + 1, r);
int sum = 0;
for(int i = l; i <= mid; i ++ ){
if(nums[i] < nums[r])
break;
for(int j = mid + 1; j <= r; j ++ ){
if(nums[i] > nums[j]){
sum += r - j + 1;
break;
}
}
}
return left + right + sum;
}
void quickSort(vector<int>& nums, int l, int r){
if(l >= r)return;
int i = l - 1, j = r + 1, pivot = nums[(l + r) / 2];
while(i < j){
while(nums[++ i] > pivot);
while(nums[-- j] < pivot);
if(i < j)swap(nums[i], nums[j]);
}
quickSort(nums, l, j), quickSort(nums, j + 1, r);
}
};
归并排序改良(击败96 + 93)
class Solution {
public:
int temp[50010] = {0};//初始化temp数组
int reversePairs(vector<int>& nums) {
if(nums.size() < 2) return 0;//防止越界
return reverseP(nums, 0, nums.size() - 1);
}
int reverseP(vector<int>& nums, int l, int r){/[l, r]左闭右闭
if(l == r)return 0;//当l == r时相当于区间内只有1个数字,返回0
int mid = l + (r - l) / 2; // 这样写的好处是防止溢出
int left = reverseP(nums, l, mid);
int right = reverseP(nums, mid + 1, r);//首先获得左右区间内的逆序对数量
int sum = 0;
//接下来基本就是y总归并排序的模板
int i = l, j = mid + 1, k = 0;
while(i <= mid && j <= r){
if(nums[i] <= nums[j])
temp[k ++ ] = nums[i ++ ];
else{
sum += mid - i + 1;//若nums[i] > nums[j],那么从[i, mid]的所有mus[i]都大于nums[j]
temp[k ++ ] = nums[j ++ ];
}
}
while(i <= mid)temp[k ++ ] = nums[i ++ ];
while(j <= r)temp[k ++ ] = nums[j ++ ];
for(i = l, k = 0; i <= r; i ++, k ++ )nums[i] = temp[k];
return left + right + sum;
}
};