AcWing788.逆序對的數量（Java）

題目來源：https://www.acwing.com/problem/content/790/

題目描述

給定一個長度為 n 的整數數列，請你計算數列中的逆序對的數量。

逆序對的定義如下：對於數列的第 i 個和第 j個元素，如果滿足 i<j且 a[i]>a[j]，則其為一個逆序對；否則不是。

輸入格式

第一行包含整數 n，表示數列的長度。

第二行包含 n個整數，表示整個數列。

輸出格式

輸出一個整數，表示逆序對的個數。

數據範圍

1≤n≤100000 數列中的元素的取值範圍 1∼10^9

輸入樣例：

6
2 3 4 5 6 1

輸出樣例：

5

思路講解

1. 首先還是理解下題意吧，通俗點講，逆序對就是指，一個數組中的兩個數，如果前面的數大於後面的那個數，那麼這兩個數就組成一個逆序對

2. 求逆序對的演算法是利用了分治的思想,在分治的過程中會將序列分為兩部分，此時逆序對可以分為三種情況：兩個數都在左邊的（設為s1）。兩個數都在右邊的（s2），一個數在左邊一個數在右邊的(s3)。現在假設我們在歸併排序的時候寫的函數merge_sort(int[] q, int left, int right)可以返回l到r區間中逆序對數量。那麼s1便是左半邊的返回值，s2則是右半邊的返回值，而s3卻無法如此得到，因為s3不知道跨度是什麼。那麼核心問題就在於怎麼求s3，以及怎麼使我們的merge_sort(int[] arr, int l, int r)可以返回l到r區間中逆序對數量。

3. 我們應當確定的是，再歸併排序中，其下等待歸併的所有小數組，結尾有序數組，也就是說，若a數組中的a1大於b數組中的b1，那麼a2，a3······都會是大於b1的，那麼我們就會很自然的得到res(最終結果)=mid-i+1。

4. 而我們是如何得到情況s1和s2的呢？很顯然的是，在遞歸過程中，s1與s2其實是處於s3的狀態的，因此很輕易的就可以得到上述結論

5. 需要強調的幾點是

   • 即使我們是求逆序對數量，也應當在排序後進行“掃尾”工作，以確保後續遞歸的正常進行

   • 由於我們求的是逆序對，所以我們應當將方法返回值設為long類型，因為本題數據範圍1≤n≤100000，若數組為降序數組，int類型無法滿足要求，應設置為long，

    

代碼

import java.util.Scanner;
​
public class Main {
    //開闢足夠大的數組空間
    static int N = 100010;
    static int[] q = new int[N], temp = new int[N];
    public static void main(String[] args) {
        //輸入數組大小以及數組的值
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            q[i] = sc.nextInt();
        }
​
        //運行方法並輸出結果
        System.out.println(merge_sort(q,0,n-1));
    }
​
    public static long  merge_sort(int []q,int left,int right) {
        //進行判斷
        if (left >= right) return 0;
​
        //進行遞歸，將數組分為最小單位的值,接著在從最小進行排序，逐漸到整個數組
        int mid = left + (right - left) / 2;
​
        //確立返回值
        long res = merge_sort(q,left,mid) + merge_sort(q,mid+1,right);
​
        int i = left, j = mid + 1;//建立雙指針，i指向前一個數，j指向後一個數
        int k = 0;//令temp從0開始，往其中添加元素
​
        //進行歸併操作，將數存放至臨時數組temp
        while (i <= mid && j <= right) {//確認邊界
            if (q[i] <= q[j])
                temp[k++] = q[i++];
            else{
                temp[k++] = q[j++];
                res += mid - i + 1;
            }
        }
        //防止i或j提前用光的情況發生，並保持後續數組排列正確
        while (i <= mid) temp[k++] = q[i++];
        while (j <= right) temp[k++] = q[j++];
​
        for(i = left, k = 0; i <= right; i ++, k ++) q[i] = temp[k];//把原數組未排序的部分覆蓋成已排序部分
        return res;
    }
}
​
​

個人失誤

  while (i <= mid && j <= right) {//確認邊界
            if (q[i] <= q[j])
                temp[k++] = q[i++];
            else{
                temp[k++] = q[j++];
                res += mid - i + 1;
            }
        }

這裡else寫的時候忘記{}了，直接導致無論怎樣res都會直接加，導致出錯