【算法】acwing788 逆序对的数量(模板题)

原题连接

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。

第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000，
数列中的元素的取值范围 [1,109]。

输入样例：
6
2 3 4 5 6 1
输出样例：
5

此题时归并排序的变题，回顾一手归并code

import java.util.*;

public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] a = new int [n];
        for(int i = 0; i < n; i ++){
            a[i] = sc.nextInt();
        }

        mergeSort(a,0,n-1);

        for(int i = 0; i < n; i ++)System.out.print(a[i] + " ");

    }

    public static void mergeSort(int [] a, int l, int r){
        if(l >= r)return;
        int x =  l + r >> 1;

        mergeSort(a,l,x);
        mergeSort(a,x+1,r);

        int [] t = new int [r-l+1];

        int i = l, j = x + 1, k = 0;//双指针

        while(i <= x && j <= r ){
            if(a[i] <= a[j]){
                t[k ++] = a[i ++];
            }else{
                t[k ++] = a[j ++];
            }
        }
        while(i <= x)t[k++] = a[i++];
        while(j <= r)t[k++] = a[j++];

        for(int y = l,z = 0; y <=  r; y++, z++)a[y]=t[z];
    }
}

本题思路：利用分治思想，再归并时统计逆序对数量。

我们将序列从中间分开，将逆序对分成三类：

1. 两个元素都在左边；
   2两个元素都在右边；
   两个元素一个在左一个在右；

因此这就是我们算法的大致框架：

计算逆序对的数量（序列）：

1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。

这个时候我们注意到一个很重要的性质，左右半边的元素在各自任意调换顺序，是不影响第三步计数的，因此我们可以数完就给它排序。这么做的好处在于，如果序列是有序的，会让第三步计数很容易。
如果无序暴力数的话这一步是O(n^2)的。

ac coed

import java.io.*;

public class Main{
    static int N = 100010; 
    static int[] a = new int[N];

    public static void main(String[] args)throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String[] arrStr = bf.readLine().split(" ");
        for (int i = 0; i < n; i++)a[i] = Integer.parseInt(arrStr[i]);

        System.out.println(mergeSort(0,n - 1));
        bf.close();
    }

    public static long mergeSort(int l,int r){
        if(l >= r)return 0;

        int mid = l + r >> 1;
        long res = 0;

        //情况一和情况二，对左右数组排序
        res += mergeSort(l,mid) + mergeSort(mid + 1,r);

        //归并过程
        int[] tmp = new int[r - l + 1];

        int i = l,j = mid + 1, k = 0;

        while(i <= mid && j <= r){
            if(a[i] <= a[j])tmp[k ++] = a[i ++];
            else{
                tmp[k ++] = a[j ++];

                //情况三
                res += mid - i + 1;
            }
        }

        //扫尾过程
        while(i <= mid)tmp[k ++] = a[i ++];
        while(j <= r)tmp[k ++] = a[j ++];

        //物归原主
        for(int x = l,y = 0; x <= r; x ++ ,y ++)a[x] = tmp[y];
        return res;

    }
}

时间复杂度o(nlogn)