題目描述 在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007
輸入描述:
題目保證輸入的數組中沒有的相同的數字
數據范圍：
對于%50的數據,size<=10^4 對于%75的數據,size<=10^5 對于%100的數據,size<=2*10^5
輸入例子:
1,2,3,4,5,6,7,0
輸出例子:
7
算法解析： 這個時候，最直觀的解法必然是用順序掃描，但是往往最直觀的不是最好的，我們這里舉個栗子：數組[7, 5, 6, 4， 3， 2， 4， 1]， 我們先考慮兩個相鄰的數字是否是逆序對，比如[7, 5], [6, 4], [3, 2], [4, 1], 這4個子數組，我們對其進行判定后，合并排序，同時統計逆序，然后形成四個子數組為[5, 7], [4, 6], [2, 3], [1, 4],這時候因為我們是順序分解的子數組，所以兩個子數組之間同樣要統計逆序，比如[5, 7] 和[4, 6]，[2, 3] 和[1, 4]，因為逆序對，是前一個數字比后邊的數字大形成逆序對，而現在的子數組又是從小到大有序的，那么就可以將遍歷起點放到兩個子數組的末尾，如果前一個子數組的末尾比后一個子數組的末尾大，則代表前一個數組的末尾數字對后邊的子數組的每一個數字都形成逆序對。如果前一個子數組的遍歷指針指向的值比后邊子數組遍歷指針指向的值小，則代表可能含有逆序對，但是需要在后一個子數組中向前查找，當然最后需要修改數組的值，不然會發生重復統計的問題。這個過程就類似歸并排序。 代碼如下：
public static int InversePairs(int [] array) { if (array == null || array.length <= 1){ return 0; } int[] temp = new int[array.length]; int count = mergeSort(temp, array, 0, array.length - 1); return (count % 1000000007); } PRivate static int mergeSort(int[] temp, int[] array, int start, int end) { if (start >= end){ return 0; } int mid = (start + end) >> 1; int leftCount = mergeSort(temp, array, start, mid)%1000000007; int rightCount = mergeSort(temp, array, mid + 1, end)%1000000007; int count = 0; int leftP = mid; int rightP = end; int copyP = end; while (leftP >= start && rightP > mid){ if (array[leftP] > array[rightP]){ count += rightP - mid; temp[copyP --] = array[leftP --]; if (count >= 1000000007){ count %= 1000000007; } }else{ temp[copyP --] = array[rightP --]; } } for (; leftP >= start; leftP--) { temp[copyP --] = array[leftP]; } for (; rightP > mid; rightP--) { temp[copyP --] = array[rightP]; } for (int i = start; i <= end; i++) { array[i] = temp[i]; } return (leftCount + rightCount + count) % 1000000007; }新聞熱點
疑難解答
