在陣列中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對，輸入一個陣列，求出這個陣列中的逆序對的總數 P，并將 P 對 1000000007 取模的結果輸出， 即輸出 P % 1000000007
示例：
輸入
1,2,3,4,5,6,7,0
輸出
7
解題思路
通過歸并排序的思想來求解，把資料分成前后兩個陣列（遞回分到每個陣列僅有一個資料項），合并時，如果前面的陣列值 array[i] 大于后面陣列值 array[j]，則前面 陣列array[i] ~ array[mid] 都是大于array [j] 的，count += mid - i + 1
public class Solution {
private int count = 0;
public int InversePairs(int[] array) {
if(array != null && array.length > 0) {
mergeSort(array, new int[array.length], 0, array.length - 1);
}
return count;
}
public void merge(int[] array, int[] temp, int low, int mid, int high) {
int i = low, j = mid + 1;
int index = low;
while (i <= mid && j <= high) {
if (array[i] > array[j]) {
count += mid - i + 1;
temp[index++] = array[j++];
if(count >= 1000000007) {
count %= 1000000007;
}
} else {
temp[index++] = array[i++];
}
}
while (i <= mid) {
temp[index++] = array[i++];
}
while (j <= high) {
temp[index++] = array[j++];
}
for(i = low; i <= high; i++) {
array[i] = temp[i];
}
}
public void mergeSort(int[] array, int[] temp, int low, int high) {
if(low >= high) {
return;
}
int mid = (low + high) / 2;
mergeSort(array, temp, low, mid);
mergeSort(array, temp, mid + 1, high);
merge(array, temp, low, mid, high);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/178073.html
標籤：其他