题目描述

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

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

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

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

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

数据范围
1≤n≤100000

样例

输入样例：

6
2 3 4 5 6 1

输出样例：

5

算法1（归并排序）

思路

a[i]：区间一上的点
a[j]：区间二上的点

1.在归并排序时，因为两个区间都是升序的，
因此如果a[j] < a[i],则a[i]及a[i]后面所有点都是a[j]的逆序对,j++

2.如果a[i] <= a[j],则不构成逆序对,i++ （注意=时也是i走，否则会漏掉一个j！）

3.如果i走完，则j后面没有一个数与区间一构成逆序对，因为是升序的

总结：先实现归并排序，在遍历j时，找出每一个a[j]对应的逆序对

Java 代码

import java.util.*;

public class Main{
    private static int N = 100010;
    private static int[] a = new int[N];
    private static int[] t = new int[N];
    private static long num = 0;
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        for(int i = 0;i < n;i++){
            a[i] = scanner.nextInt();
        }
        int l = 0,r = n-1;
        mergeSort(a,l,r);
        System.out.print(num);

    }
    public static void mergeSort(int[] a,int l,int r){
        if(l >= r){
            return;
        }
        int m = l + r >> 1;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);
        int i = l,j = m + 1,k = 0;
        int q = j;
        while(i <= m && j <= r){
            if(a[j] < a[i]){
                num += m - i + 1;
            }
            //这里a[i]和a[j]相等时必须移动a[i]，否则会漏掉一个j
            t[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        }
        while(i <= m){
            t[k++] = a[i++];
        }
        while(j <= r){
            t[k++] = a[j++];
        }
        for(i = l,k = 0;i <= r;i++,k++){
            a[i] = t[k];
        }
    }
}