leetcode 困难 —— 数组中的逆序对（分治法）

题目：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

题解：
① 我最开始想的蠢方法（会超时，可跳过）
首先题目求的逆序对，这考虑的关键应该就是 位置 和 大小

那么我们先将大小排个序，然后从小到大考虑

然后我们按数字从小到大放到由位置排序的容器中
每一次放入，二分搜索当前要放入值的位置，其之后的值的数量，就是该值组成的逆序对数量
这样是不是可以只用考虑位置（因为之前放入容器的值的大小都小于当前值）

这样排序 O(nlogn)，然后每次放入值前二分搜索 O(nlogn)，但是还是超时了
应该是那个 insert 复杂度太高了，没办法，vector 的 insert 复杂度为 O(n)
想过用其他容器，但好像都不能解决，要是大佬有方法，欢迎评论私信，真想不出来 😟

代码如下：

class Solution {
public:vector<pair<int, int> > temp1;vector<pair<int, int> > temp2;int reversePairs(vector<int>& nums) {int res = 0;for(int i = 0; i < nums.size(); i++) {temp1.push_back(make_pair(nums[i], i));}sort(temp1.begin(), temp1.end());for(int i = 0; i < temp1.size(); i++) {pair<int, int> t = make_pair(temp1[i].second, temp1[i].first);int f = lower_bound(temp2.begin(), temp2.end(), t) - temp2.begin();res = res + i - f;temp2.insert(temp2.begin() + f, t);}return res;}
};

② 分治法（害，我这笨脑子，真的想不到啊）
分治排序都知道吧
我们在排序的过程中，考虑逆序对数量

首先两个有序的序列，求逆序对数量
左边的序列中的某个值所组成逆序对等于右边所有小于它的值的数量

可以通过分治法求解的原理，即
局部的排序，不会影响这部分和其他部分组成逆序对

代码如下：

class Solution {
public:vector<int> numbers;int res = 0;void solve(int l, int r) {int mid = (r + l) / 2;if(r - l > 1) {solve(l, mid);solve(mid, r);}else {return;}vector<int> temp;int flag1 = l, flag2 = mid;while(flag1 < mid) {while(flag2 < r && numbers[flag1] > numbers[flag2]) {temp.push_back(numbers[flag2]);flag2++;}temp.push_back(numbers[flag1]);flag1++;res = res + flag2 - mid;}while(flag2 < r) {temp.push_back(numbers[flag2]);flag2++;}for(int i = l; i < r; i++) {numbers[i] = temp[i - l];}}int reversePairs(vector<int>& nums) {numbers = nums;solve(0, nums.size());return res;}
};