題目描述 [數(shù)組中的逆序?qū)
在數(shù)組中的兩個(gè)數(shù)字，如果前面一個(gè)數(shù)字大于后面的數(shù)字，則這兩個(gè)數(shù)字組成一個(gè)逆序?qū)?。輸入一個(gè)數(shù)組,求出這個(gè)數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對(duì)1000000007取模的結(jié)果輸出。 即輸出P%1000000007
解題思路
轉(zhuǎn)自 https://www.cnblogs.com/coffy/p/5896541.html
分治思想，采用歸并排序的思路來(lái)處理，如下圖，先分后治：
先把數(shù)組分解成兩個(gè)長(zhǎng)度為2的子數(shù)組，再把這兩個(gè)子數(shù)組分解成兩個(gè)長(zhǎng)度為1的子數(shù)組。接下來(lái)一邊合并相鄰的子數(shù)組，一邊統(tǒng)計(jì)逆序?qū)Φ臄?shù)目。在第一對(duì)長(zhǎng)度為1的子數(shù)組{7}、{5}中7>5，因此（7,5）組成一個(gè)逆序?qū)ΑＭ瑯釉诘诙?duì)長(zhǎng)度為1的子數(shù)組{6}，{4}中也有逆序?qū)Γ?,4），由于已經(jīng)統(tǒng)計(jì)了這兩對(duì)子數(shù)組內(nèi)部的逆序?qū)?，因此需要把這兩對(duì)子數(shù)組進(jìn)行排序，避免在之后的統(tǒng)計(jì)過(guò)程中重復(fù)統(tǒng)計(jì)。
逆序?qū)Φ目倲?shù)=左邊數(shù)組中的逆序?qū)Φ臄?shù)量+右邊數(shù)組中逆序?qū)Φ臄?shù)量+左右結(jié)合成新的順序數(shù)組時(shí)中出現(xiàn)的逆序?qū)Φ臄?shù)量；
總結(jié)統(tǒng)計(jì)數(shù)組逆序?qū)Φ倪^(guò)程：先把數(shù)組分隔成子數(shù)組，先統(tǒng)計(jì)出子數(shù)組內(nèi)部的逆序?qū)Φ臄?shù)目，然后再統(tǒng)計(jì)出兩個(gè)相鄰子數(shù)組之間的逆序?qū)Φ臄?shù)目。在統(tǒng)計(jì)逆序?qū)Φ倪^(guò)程中，還需要對(duì)數(shù)組進(jìn)行排序，其實(shí)這個(gè)排序過(guò)程就是歸并排序的思路。
代碼
class Solution {
public:
int InversePairs(vector<int> data) {
int size = data.size();
if (size <= 1) return 0;
vector<int> tmp = data;
int resu = InversePairsCore(data, tmp, 0, size - 1);
return resu;
}
int InversePairsCore(vector<int> &data, vector<int> &tmp, int start, int end) {
if (start == end) {
tmp[start] = data[start];
return 0;
}
int mid = (start + end) / 2;
int low = InversePairsCore(tmp, data, start, mid);
int high = InversePairsCore(tmp, data, mid + 1, end);
int i = mid, j = end, index = end;
long long cnt = 0;
while (i >= start && j >= (mid + 1)) {
if (data[i] > data[j]) {
tmp[index--] = data[i--];
cnt += j - mid;
}
else {
tmp[index--] = data[j--];
}
}
for (; i >= start; i--) {
tmp[index--] = data[i];
}
for (; j >= (mid + 1); j--) {
tmp[index--] = data[j];
}
return (low + high + cnt) % 1000000007;
}
};
