##題目描述 在陣列中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對，輸入一個陣列,求出這個陣列中的逆序對的總數P， 并將P對1000000007取模的結果輸出，即輸出P%1000000007，
輸入描述:
題目保證輸入的陣列中沒有的相同的數字，
資料范圍：
對于%50的資料,size<=10^4
對于%75的資料,size<=10^5
對于%100的資料,size<=2*10^5
思路
分治法，歸并排序，
時間復雜度O(nlgn)，空間復雜度O(n)，
代碼
public class Solution {
private int val;
private int[] tmp;
//二路歸并
private void divide(int[] arr, int start, int end) {
if(start >= end) return;
int mid = (start + end) >> 1;
divide(arr, start, mid);
divide(arr, mid + 1, end);
merge(arr, start, mid, end);
}
//歸并排序
private void merge(int[] arr, int start, int mid, int end) {
int k = 0, l = start, r = mid + 1;
while(l <= mid && r <= end) {
//原歸并排序的核：tmp[k++] = arr[l] < arr[r] ? arr[l++] : arr[r++];
if(arr[l] > arr[r]) {
val = (val + mid + 1 - l)%1000000007;
tmp[k++] = arr[r++];
} else {
tmp[k++] = arr[l++];
}
}
while(l <= mid) tmp[k++] = arr[l++];
while(r <= end) tmp[k++] = arr[r++];
for(int i = start; i <= end; i++) {
arr[i] = tmp[i-start];
}
}
public int InversePairs(int [] array) {
if(array == null || array.length == 0) return 0;
val = 0;
tmp = new int[array.length];
divide(array, 0, array.length-1);
return val;
}
}
筆記
遞回先寫遞回出口，再寫遞回運行框架，最后實作遞回操作細節，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/83473.html
標籤：其他
上一篇：第一個只出現一次的字符