题解 | #数组中的逆序对#

C++版本： 本质上是归并排序的拓展，merge的时候，后<前，则逆序对数量+=前剩下的所有数(M-P1+1) class Solution { public: int inverseCount = 0; void merge(vector& data, int L, int M, int R) { vector help(R - L + 1,0); int p1 = L, p2 = M + 1; int i = 0; while (p1 <= M && p2 <= R) { if (data[p2] < data[p1]) { inverseCount+=(M-p1+1); inverseCount%=1000000007; help[i++] = data[p2++]; } else{ help[i++] = data[p1++]; } } while (p1 <= M) { help[i++] = data[p1++]; } while (p2 <= R) { help[i++] = data[p2++]; } for (i = 0; i < help.size(); i++) { data[L + i] = help[i]; } } void mergeCore(vector& data, int L, int R) { if (L == R) return; int M = L + (R - L) /2; mergeCore(data, L, M); mergeCore(data, M+1, R); merge(data, L, M, R); }

int InversePairs(vector &data) { if (data.size() <= 1) return 0; mergeCore(data, 0, data.size() - 1); return inverseCount; } };