題目：在數(shù)組中的兩個數(shù)字砰粹，如果前面一個數(shù)字大于后面的數(shù)字唧躲，則這兩個數(shù)字組成一個逆序對。輸入一個數(shù)組,求出這個數(shù)組中的逆序對的總數(shù)P碱璃。并將P對1000000007取模的結果輸出弄痹。 即輸出P%1000000007
輸入描述:
題目保證輸入的數(shù)組中沒有的相同的數(shù)字
數(shù)據(jù)范圍：
對于%50的數(shù)據(jù),size<=10^4
對于%75的數(shù)據(jù),size<=10^5
對于%100的數(shù)據(jù),size<=2*10^5
示例1
輸入
1,2,3,4,5,6,7,0
輸出
7
public class Solution {
public int InversePairs(int [] array) {
if(array == null || array.length == 0){
return 0;
}
int[] copy = new int[array.length];
for(int i = 0; i < array.length; i++){
copy[i] = array[i];
}
int count = helper(array, copy, 0, array.length - 1);
return count;
}
int helper(int[] array, int[] copy, int low, int high){
if(low == high){
return 0;
}
int mid = (low + high) >> 1;
int leftCount = helper(array, copy, low, mid) % 1000000007;
int rightCount = helper(array, copy,mid + 1, high) % 1000000007;
int count = 0;
int i = mid;
int j = high;
int locCopy = high;
while(i >= low && j > mid){
if(array[i] > array[j]){
count += j - mid;
copy[locCopy--] = array[i--];
if(count >= 1000000007){
count%=1000000007;
}
}
else{
copy[locCopy--] = array[j--];
}
}
for(; i>=low;i--){
copy[locCopy--] = array[i];
}
for(;j>mid;j--){
copy[locCopy--]=array[j];
}
for(int s = low; s<=high;s++){
array[s] = copy[s];
}
return (leftCount +rightCount + count) % 1000000007;
}
}
牛客里有一個很好的回答
鏈接：https://www.nowcoder.net/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
來源：徘镀鳎客網(wǎng)
思路分析：
看到這個題目肛真，我們的第一反應是順序掃描整個數(shù)組。沒掃描到一個數(shù)組的時候爽航，逐個比較該數(shù)字和它后面的數(shù)字的大小蚓让。如果后面的數(shù)字比它小乾忱，則這兩個數(shù)字就組成了一個逆序對。假設數(shù)組中含有n個數(shù)字历极。由于每個數(shù)字都要和O(n)這個數(shù)字比較窄瘟，因此這個算法的時間復雜度為O(n^2)。
我們以數(shù)組{7,5,6,4}為例來分析統(tǒng)計逆序對的過程执解。每次掃描到一個數(shù)字的時候寞肖，我們不拿ta和后面的每一個數(shù)字作比較，否則時間復雜度就是O(n^2)衰腌，因此我們可以考慮先比較兩個相鄰的數(shù)字。
(a) 把長度為4的數(shù)組分解成兩個長度為2的子數(shù)組觅赊；
(b) 把長度為2的數(shù)組分解成兩個成都為1的子數(shù)組右蕊；
(c) 把長度為1的子數(shù)組 合并、排序并統(tǒng)計逆序對 吮螺；
(d) 把長度為2的子數(shù)組合并饶囚、排序，并統(tǒng)計逆序對鸠补；
在上圖（a）和（b）中萝风，我們先把數(shù)組分解成兩個長度為2的子數(shù)組，再把這兩個子數(shù)組分別拆成兩個長度為1的子數(shù)組紫岩。接下來一邊合并相鄰的子數(shù)組规惰，一邊統(tǒng)計逆序對的數(shù)目。在第一對長度為1的子數(shù)組{7}泉蝌、{5}中7大于5歇万，因此（7,5）組成一個逆序對。同樣在第二對長度為1的子數(shù)組{6}勋陪、{4}中也有逆序對（6,4）贪磺。由于我們已經(jīng)統(tǒng)計了這兩對子數(shù)組內(nèi)部的逆序對，因此需要把這兩對子數(shù)組 排序 如上圖（c）所示诅愚， 以免在以后的統(tǒng)計過程中再重復統(tǒng)計寒锚。
接下來我們統(tǒng)計兩個長度為2的子數(shù)組子數(shù)組之間的逆序對。合并子數(shù)組并統(tǒng)計逆序對的過程如下圖如下圖所示违孝。
我們先用兩個指針分別指向兩個子數(shù)組的末尾刹前，并每次比較兩個指針指向的數(shù)字。如果第一個子數(shù)組中的數(shù)字大于第二個數(shù)組中的數(shù)字等浊，則構成逆序對腮郊，并且逆序對的數(shù)目等于第二個子數(shù)組中剩余數(shù)字的個數(shù)，如下圖（a）和（c）所示筹燕。如果第一個數(shù)組的數(shù)字小于或等于第二個數(shù)組中的數(shù)字轧飞，則不構成逆序對衅鹿，如圖b所示。每一次比較的時候过咬，我們都把較大的數(shù)字從后面往前復制到一個輔助數(shù)組中大渤，確保 輔助數(shù)組（記為copy） 中的數(shù)字是遞增排序的。在把較大的數(shù)字復制到輔助數(shù)組之后掸绞，把對應的指針向前移動一位泵三，接下來進行下一輪比較。
過程：先把數(shù)組分割成子數(shù)組衔掸，先統(tǒng)計出子數(shù)組內(nèi)部的逆序對的數(shù)目烫幕，然后再統(tǒng)計出兩個相鄰子數(shù)組之間的逆序對的數(shù)目。在統(tǒng)計逆序對的過程中敞映，還需要對數(shù)組進行排序较曼。如果對排序算法很熟悉，我們不難發(fā)現(xiàn)這個過程實際上就是歸并排序振愿。
