【归并】Leetcode 交易逆序对的总数

本文主要是介绍【归并】Leetcode 交易逆序对的总数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目讲解

LCR 170. 交易逆序对的总数

---

算法讲解

还是使用分治算法的思想：我们可以先将数组分成两块，先求出左边部分的逆序对，右边部分的逆序对和一左一右的逆序对，三个数量相加就是当前数组中的所有逆序对；其次我们在求子数组逆序对的时候，可以把排序添加上，如果添加上排序，那么求左右部分的逆序对的时候就会很方便，只需要将下标相减即可

class Solution {int temp[50002];
public:int reversePairs(vector<int>& record) {return Merge(record, 0 , record.size() - 1);}int Merge(vector<int>& nums, int left, int right){int ret = 0;if(left >= right)return ret;int mid = left + (right - left) / 2;ret += Merge(nums, left, mid);ret += Merge(nums, mid+1, right);//处理一左一右 + 合并有序数组  升序int i = 0, cur1 = left, cur2 = mid+1;while(cur1 <= mid && cur2 <= right){if(nums[cur1] <= nums[cur2])temp[i++] = nums[cur1++];else{ret += mid - cur1 + 1;temp[i++] = nums[cur2++];}}//处理cur指针没有结束的数组while(cur1 <= mid)temp[i++] = nums[cur1++];while(cur2 <= right)temp[i++] = nums[cur2++];//填充原来的数组for(int k = left; k <= right; k++){nums[k] = temp[k - left];}return ret;}
};

这篇关于【归并】Leetcode 交易逆序对的总数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---