本文首發(fā)于我的個人博客：尾尾部落
題目描述
在數(shù)組中的兩個數(shù)字，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)?。輸入一個數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P。并將P對1000000007取模的結(jié)果輸出。 即輸出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
解題思路
很容易想到的方法就是遍歷每一個元素，讓其與后面的元素對比，如果大于則count++，但是這樣的時間復(fù)雜度是O(n^2)，因此，我們可以用歸并排序思路。
image
例如7,5,4,6可以劃分為兩段7,5和4,6兩個子數(shù)組
- 在7,5中求出逆序?qū)?，因?yàn)?大于5所以有1對
- 在6,4中求出逆序?qū)?，因?yàn)?大于4所以逆序?qū)υ偌?，為2
- 對7,5和6,4進(jìn)行排序，結(jié)果為5,7,和4,6
- 設(shè)置兩個指針分別指向兩個子數(shù)組中的最大值，p1指向7，p2指向6
- 比較p1和p2指向的值，如果大于p2，因?yàn)閜2指向的是最大值，所以第二個子數(shù)組中有幾個元素就有幾對逆序?qū)?當(dāng)前有兩個元素，逆序?qū)?,2+2=4)，7>6,比較完之后將p1指向的值放入輔助數(shù)組里，輔助數(shù)組里現(xiàn)在有一個數(shù)字7，然后將p1向前移動一位指向5
- 再次判斷p1和p2指向的值，p1小于p2，因?yàn)閜1指向的是第一個子數(shù)組中最大值，所以子數(shù)組中沒有能和當(dāng)前p2指向的6構(gòu)成逆序?qū)Φ臄?shù)，將p2指向的值放入輔助數(shù)組，并向前移動一位指向4，此時輔助數(shù)組內(nèi)為6,7
- 繼續(xù)判斷p1(指向5)和p2(指向4)，5>4,第二個子數(shù)組中只有一個數(shù)字，逆序?qū)?，4+1=5，為5對，然后將5放入輔助數(shù)組，第一個子數(shù)組遍歷完畢，只剩下第二個子數(shù)組，當(dāng)前只有一個4，將4也放入輔助數(shù)組，函數(shù)結(jié)束。輔助數(shù)組此時為4,5,6,7.逆序?qū)?.
參考代碼
public class Solution {
public int InversePairs(int [] array) {
int len = array.length;
if(array== null || len <= 0){
return 0;
}
return mergeSort(array, 0, len-1);
}
public int mergeSort(int [] array, int start, int end){
if(start == end)
return 0;
int mid = (start + end) / 2;
int left_count = mergeSort(array, start, mid);
int right_count = mergeSort(array, mid + 1, end);
int i = mid, j = end;
int [] copy = new int[end - start + 1];
int copy_index = end - start;
int count = 0;
while(i >= start && j >= mid + 1){
if(array[i] > array[j]){
copy[copy_index--] = array[i--];
count += j - mid;
if(count > 1000000007){
count %= 1000000007;
}
}else{
copy[copy_index--] = array[j--];
}
}
while(i >= start){
copy[copy_index--] = array[i--];
}
while(j >= mid + 1){
copy[copy_index--] = array[j--];
}
i = 0;
while(start <= end) {
array[start++] = copy[i++];
}
return (left_count+right_count+count)%1000000007;
}
}
