參考：1、 https://www.geeksforgeeks.org/merge-sort/
2、《劍指Offer：名企面試官精講典型編程題》
題目描述
在陣列中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對，輸入一個陣列,求出這個陣列中的逆序對的總數P，并將P對1000000007取模的結果輸出， 即輸出P%1000000007
輸入描述:
題目保證輸入的陣列中沒有的相同的數字
資料范圍：
- 對于%50的資料,size<=10^4
- 對于%75的資料,size<=10^5
- 對于%100的資料,size<=2*10^5
示例1 輸入：1，2，3，4，5，6，7，0 輸出：7
解題思路1 （暴力法，時間復雜度: O(n^2)）
這個方法最簡單直接，順序掃描整個陣列，每掃到一個數，逐個比較其后面的所有數，如果構成逆序對，則計數+1，代碼沒啥難度，略了，
解題思路2 （分治法，時間復雜度: O(nlogn)，空間復雜度：O(n)）
1 public int InversePairs(int[] array) { 2 if (array.length < 2) { 3 return 0; 4 } 5 return divideAndConquer(array, 0, array.length); 6 } 7 8 public int divideAndConquer(int[] array, int l, int r) { 9 if (l >= r - 1) return 0; 10 11 int mid = (l + r) / 2; 12 int count = 0; 13 int countL = divideAndConquer(array, l, mid); 14 int countR = divideAndConquer(array, mid, r); 15 int[] left = Arrays.copyOfRange(array, l, mid); 16 int[] right = Arrays.copyOfRange(array, mid, r); 17 int i = left.length - 1; 18 int j = right.length - 1; 19 for (int k = r - 1; k >= l; k--) { 20 // two cases: left is empty or right is empty 21 if (i < 0) { 22 array[k] = right[j]; 23 j--; 24 continue; 25 } else if (j < 0) { 26 array[k] = left[i]; 27 i--; 28 continue; 29 } 30 if (left[i] > right[j]) { 31 count += j + 1; 32 if (count > 1000000007) { 33 count %= 1000000007; 34 } 35 array[k] = left[i]; 36 i--; 37 } else { 38 array[k] = right[j]; 39 j--; 40 } 41 } 42 return (count + countL + countR) % 1000000007; 43 }
這一題的解法是在歸并排序(Merge Sort) 的基礎上修改得到的，Merge Sort使用的是分治法的思想，分治法 (divide and conquer) 是將一個復雜的問題，分成兩個或多個相同或者相似的子問題，再把子問題分成更小的子問題，一直分到子問題足夠簡單來求解，最后再把子問題的解合并成原問題的解，歸并排序法的時間復雜度為 O(nlogn)，空間復雜度為 臨時的陣列 + 遞回時壓入堆疊的資料占用的空間 = n + logn，即 O(n)，
以陣列 {7, 5, 6, 4} 為例進行分析，解題程序如圖5.2所示，首先將陣列拆成至長度為1的子陣列，然后一邊合并一邊統計逆序對的數目，在第一對長度為1 的子陣列 {7}、{5}中，有一對逆序對 (7, 5)，在第二對長度為1的子陣列 {6}、{4}中，也有一對逆序對(6, 4)，在統計完這兩對逆序對后，需要分別對他們進行排序，如圖 5.2(c)，以免在以后的統計程序中再重復統計，
然后需要統計兩個長度為2的子陣列之間的逆序對，并合并兩個子陣列，如圖5.3所示，兩個子陣列分別從末尾開始判斷數的大小，如圖5.2(a)中指標P1、P2，如果 P1 大于 P2，則構成逆序對，并且逆序對的數目等于第二個子陣列中剩余數字的個數，即 P2 以及之前的所有數字的個數，如果 P1 小于或等于 P2, 則不構成逆序對，每次比較的時候，我們都把較大的數字從后往前復制到一個輔助陣列，確保輔助陣列中的數字是遞增排序的，在把較大的數字復制到輔助陣列之后，把對應的指標向前移動一位，接下來進行下一輪比較，
以此類推，使用這個方法去求出其他陣列的逆序對個數，在解這一題的時候，還有一點需要注意，除了需要將總輸出結果 (count + countL + countR) 對1000000007取模，還要在計算程序中將 count += j + 1 對1000000007取模，以免count超出 Integer.MAX_VALUE，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/116926.html
標籤：其他
上一篇：libpcap 庫開發的程式只能抓取到網卡發出去的包，抓不到網卡接收到的資料包，也就是只能抓取到一個方向的資料包，有誰知道是怎么回事，程式如下