题解 | 排队唱歌

import java.util.*;
import java.lang.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static int res = 0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            res = 0;
            int N = in.nextInt();
            int[] arr = new int[N];
            for(int i=0;i<N;i++) arr[i]=in.nextInt();
            mergeSort(arr);
            System.out.println(res);
        }
    }

    public static void mergeSort(int[] arr){
        if(arr.length>1){
            int mid = arr.length/2;
            int[] left = Arrays.copyOfRange(arr,0,mid);
            int[] right = Arrays.copyOfRange(arr,mid,arr.length);
            mergeSort(left);
            mergeSort(right);
            merge(arr,left,right);
        }
    }

    public static void merge(int[] arr, int[] left, int[] right){
        int i=0,j=0,k=0;
        while(i<left.length && j<right.length){
            if(left[i]<=right[j]) arr[k++] = left[i++];
            else {
                arr[k++] = right[j++];
                res+=left.length-i;
            }
        }

        while(i<left.length) arr[k++] = left[i++];
        while(j<right.length) arr[k++] = right[j++]; 
    }
}

官方题解已经有归并排序的主思路了，我看了这个题目的题解非常少，其实更加关键的问题在于：归并排序中，怎么统计交换了多少次？在哪里加代码？

我这里给出解答：在归并排序中，两个有序数组进行merge的时候，且发生了左边的元素比右边大的情况，例如：左数组为[3,4]，右数组为[1,2]，他们合并的时候，1和2就需要跑到3和4的前面去，这其实就是相当于1和3、4交换了2次，2再和3、4交换了2次，最终形成[1,2,3,4]。除了明确维护交换次数的时机以外，还需要明确具体交换了几次，那肯定是左边数组left剩下多少元素就交换多少次（left.length-i，其中i代表左边数组已经用过的次数，例如left = [1,3,4], right = [2]，那么2其实只需要越过3、4就能到达它该呆着的地方，1在2之前就已经用过了）