题目描述

逆序对的数量

思路

逆序对

当q[i] > q[j]时.
res = mid - i + 1;

时间复杂度

nlogn

JAVA 代码

import java.util.*;
import java.io.*;

public class Main{
    public static int[] temp,q;

    public static void main(String args[])throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        temp = new int[n];
        q = Arrays.asList(in.readLine().split(" ")).stream().mapToInt(Integer::parseInt).toArray();

        long res = merge(0, n-1);

        System.out.print(res);
    }

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

        int mid = l+r>>1;

        //逆序对全在左边的情况 + 逆序对全在右边的情况
        long res = merge(l,mid) + merge(mid+1, r);

        int i = l, j = mid+1, k=0;
        while(i<= mid && j<=r){
            if(q[i]<= q[j]) temp[k++] = q[i++];
            else {
                //比较的数字在两个数组中, 如果右边大于左边.
                //那么整个[左边当前数字--> mid] 的都会小于右边这个数组
                res += mid - i + 1;
                temp[k++] = q[j++];
            }
        }
        while(i<=mid)temp[k++] = q[i++];
        while(j<=r)temp[k++] = q[j++];

        for(i =l, k=0; i<=r; i++, k++){
            q[i] = temp[k];
        }
        return res;

    }
}