文章背景：
在複習演算法及資料結構時，找到了面試筆試題目，以下我們來看看題目：
（學習影片分享：java教學影片）
在陣列中的兩個數字，如果前面一個數字大於後面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。並將P對1000000007取模的結果輸出。即輸出P 00000007
輸入描述:
題目保證輸入的數組中沒有的相同的數字
數據範圍：
對於P的數據,size<=10^4
對於u的資料,size<=10^5
對於 0的資料,size<=2*10^5
分析：
這題目很好直接求解，不過時間複雜度在o(n*n) , 最開始拿到這題沒經過思考，直接dp寫完了，然後發現，dp還不如直接求解，都是o(n*n)的複雜度，dp還佔用了2*10^5的空間，下面是直接，求法和dp ,都超時了。
（更多相關面試題推薦：java面試題目及答案）
#程式碼分享：
//直接求法 ,超时
public class solution{
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
sum += 1;
}
}
sum %= 1000000007;
}
}
}public class solution{
//一维数组dp
public static int sum;
public static int InversePairs(int [] array) {
dp(array);
return sum;
}
public static int count[] = new int[200004];
public static void dp(int []array){
for(int i = array.length - 1 ; i > 0 ; i --){
for(int j = i - 1 ; j >= 0 ; j--){
if(array[j] > array[i]){
count[j] = count[j+1]+1;
}else {
count[j] = count[j+1];
}
}
sum += count[0];
sum %= 1000000007;
for(int k = 0 ; k < array.length ; k ++)
count[k] = 0;
}
}
}dp在這裡都是多餘的，
下面是歸併排序解決問題，不了解歸併排序可以看我前一篇博客 歸併排序：
public class solution{
//归并排序AC
public static int cnt ;
public static int InversePairs(int [] array) {
if(array != null){
RecusionSorted(array,0,array.length - 1);
}
return cnt%1000000007;
}
public static void MegerArray(int[] data, int start, int mid, int end) {
int temp[] = new int[end-start+1];
int i = mid;
int j = end;
int m = mid+1;
int z = 0;
while(j >= m && i >= start) {
if(data[i] > data[j]) {
temp[z++] = data[i--];
cnt += (j-mid)%1000000007;
cnt %= 1000000007;
}else {
temp[z++] = data[j--];
}
}
while(j >= m) {
temp[z++] = data[j--];
}
while(i >= start) {
temp[z++] = data[i--];
}
for(int k = start ; k <= end ; k ++) {
data[k] = temp[end - k];
}
}
public static void RecusionSorted(int data[] , int start , int end ) {
if(start < end) {
int mid = (start + end) >> 1;
RecusionSorted(data,start,mid);
RecusionSorted(data,mid+1,end);
MegerArray(data,start,mid,end);
}
}
}相關推薦：java入門教程
以上是java面試之歸併排序的應用的詳細內容。更多資訊請關注PHP中文網其他相關文章！
