算法练习：JZ51 数组中的逆序对

分析：

题干两个坑：

• 数组长度最大$10^5$；

• P的值可能超过整型数据范围；

作为归并排序的变式。

为什么能用归并排序找到逆序对？因为归并排序的重组步骤中，左数组与右数组是有序的，对两个子数组的元素排序时，若左子数组元素更大，则它右侧剩余元素也一定比右子树当前元素大。它们都能构成逆序对。如：

[3,4,5] [1,6,7]中3大于1，则3右侧的4和5一定也大于1。

思路：超时，这种题的输入序列长度基本就决定了不能用双重循环

class Solution {
public:int InversePairs(vector<int> data) {// Step0.特殊情况处理int c_count = 0;    // 表示count/100000007int count = 0;// Step1.遍历data，对比大小并计数for(int i=0; i<data.size(); i++){for(int j=i+1; j<data.size(); j++){count = ((data[i]>data[j]) ? count+1 : count);if(count % 100000007 == 0){count = 0;c_count ++;}}}return count;}
};

思路：归并排序的变式

class Solution {
public:void merge_sort(vector<int> &data, int &P, int left, int right){// Step0.递归结束条件if(left >= right) return;// Step1.进入子问题int mid = (left + right) / 2;merge_sort(data, P, left, mid);merge_sort(data, P, mid+1, right);// Step2.回溯vector<int> temp;   // 存放本轮的左右数组排序结果int l1 = left;  // 左数组的首元素下标int l2 = mid+1;  // 右数组的首元素下标for(int i=left; i<=right; i++)     // 遍历左右两个数组，进行排序{if(l1 > mid){   // 左数组遍历结束temp.push_back(data[l2]);l2++;}else if(l2 > right){   // 右数组遍历结束temp.push_back(data[l1]);l1++;}else if(data[l1] <= data[l2]){     // 左数组的元素更小temp.push_back(data[l1]);l1++;}else{   // 左数组的元素更大temp.push_back(data[l2]);l2++;P += mid - l1 + 1;	// 若左数组该元素>右数组某个元素，则左数组中[l1,mid]的元素>右数组该元素}}for(int i=0; i<=right-left; i++)    // 将排序结果复制到原数组{data[left+i] = temp[i];}P %= 1000000007;}int InversePairs(vector<int> data) {// Step0.特殊情况处理if(data.empty() or data.size()==1) return 0;int P = 0;// Step1.归并排序merge_sort(data, P, 0, data.size()-1);return P;}
};