溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
題目描述：
在數組中的兩個數字，如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并將P對1000000007取模的結果輸出。 即輸出P%1000000007
解題思路：
一開始一頭霧水，后面想到了使用歸并排序的思想，其實有多少個逆序對，就是歸并排序的時候，后面的數要超越前面多少個，嗯，好像不是很好說，要不然直接看代碼吧。還要注意，題目當中說要輸出取模的結果，這說明數據可能非常大，所以如果只是單純的在最后取模的話可能還是無法避免數據太大的影響，所以我們在每次更新count的時候就對其進行取模運算。
剛好又練習了一遍歸并排序，記錄一下
public class Solution {
int count;
public int InversePairs(int [] array) {
count = 0;
if(array != null){
divPairs(array, 0, array.length-1);
}
return count%1000000007;
}
public void divPairs(int[] array, int start, int end){
if(start >= end)
return;
int mid = (start + end)>>1;
divPairs(array, start, mid);
divPairs(array, mid+1, end);
mergePairs(array, start, mid, end);
}
public void mergePairs(int[] array, int start, int mid, int end){
int i = start, j = mid+1, k = 0;
int[] temp = new int[end-start+1];
while(i <= mid && j <= end){
if(array[i] <= array[j]){
temp[k++] = array[i++];
}else{
temp[k++] = array[j++];
count += mid - i + 1;
count %= 1000000007;
}
}
while(i <= mid){
temp[k++] = array[i++];
}
while(j <= end){
temp[k++] = array[j++];
}
for(int x = 0; x < temp.length; x++){
array[start+x] = temp[x];
}
}
}
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持億速云。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
