Leetcode 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]
输出: 5

记录一下归并排序的做法。思路就是在归并的时候记录逆序对。由于在归并的时候左右两个数组都已经升序排号，因此在对右边数组进行归并的时候，左边数组的元素都大于该元素，记录此时左边数组元素的个数即可。
直接在归并排序进行操作，增加方法的返回值即可。

class Solution {
    public int reversePairs(int[] nums) {
        if(nums==null||nums.length<=1) return 0;
       return mergesort(nums,0,nums.length-1);

    }
    public int mergesort(int[] nums,int left,int right){
        if(left>=right) return 0;
        int mid=(left+right)>>>1;
        int leftcount=mergesort(nums,left,mid);
        int rightcount=mergesort(nums,mid+1,right);
        int crosscount=merge(nums,left,right,mid);
        return leftcount+rightcount+crosscount;
    }
    public int merge(int[] nums,int left,int right,int mid){
        int count=0;
        int i=left;
        int j=mid+1;
        int k=0;
        int[] tmp=new int[right-left+1];
        while(i<=mid&&j<=right){
            if(nums[i]<=nums[j]){
                tmp[k++]=nums[i++];
            }
            else{
                tmp[k++]=nums[j++];
                count+=mid-i+1;
            }
        }
        while(i<=mid){
            tmp[k++]=nums[i++];
        }
        while(j<=right){
            tmp[k++]=nums[j++];
        }
        for(int ii=0;ii<tmp.length;ii++){
            nums[left+ii]=tmp[ii];
        }
        return count;
    }
}

题目连接

本文地址：https://blog.csdn.net/qq_44837971/article/details/107286975