AcWing 65 数组中的逆序对
程序员文章站
2022-05-13 19:34:04
...
题目描述:
在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数。
样例
输入:[1,2,3,4,5,6,0]
输出:6
分析:
暴力做法,平方级复杂度,不予考虑。采用分治法优化,类似于归并排序的思路。假设merge函数可以返回一个区间内逆序对的个数,那么对于区间[l,r],我们划分为[l,mid]和[mid+1,r]两部分,最后逆序对的个数等于左边区间逆序对数目+右边区间逆序对数目+合并时逆序对的数目,比如456 123,合并时,左边4 > 1,由于归并排序时各个子区间必然是有序的,所以4是左边区间最小的数,4 > 1说明了4右边的所有数均大于1,一共mid - i + 1个数(i为指向4的指针),次数右指针右移到指向2,继续比较,以此类推。
class Solution {
public:
int merge(vector<int> &nums,int l,int r){
if(l >= r) return 0;
int mid = l + r >> 1;
int res = merge(nums,l,mid) + merge(nums,mid + 1,r);
int i = l,j = mid + 1;
vector<int> temp;
while(i <= mid && j <= r){
if(nums[i] <= nums[j]) temp.push_back(nums[i++]);
else{
temp.push_back(nums[j++]);
res += mid - i + 1;
}
}
while(i <= mid) temp.push_back(nums[i++]);
while(j <= r) temp.push_back(nums[j++]);
i = l;
for(auto x : temp) nums[i++] = x;
return res;
}
int inversePairs(vector<int>& nums) {
return merge(nums,0,nums.size() - 1);
}
};
上一篇: vue项目运行 $ npm run dev 报错解决方案
下一篇: 归并排序