leetcode 51 数组中的逆序对

public class Solution {
    public int reversePairs(int[] nums) {
        int len=nums.length;
        if(len){//如果只有0个或1个说明不存在
            return 0;
        }
        int []copy=new int[len];
        for(int i=0;i){
            copy[i]=nums[i];
        }
        int[] tmp=new int[len];
        return reversePairs(nums,0,len-1,tmp);
    }
    public int reversePairs(int[] nums,int left,int right,int[]tmp){
        if(left==right){
            return 0;
        }
        int mid=left+(right-left)/2;
        int leftnum=reversePairs( nums, left,mid,tmp);
        int rightnum=reversePairs(nums, mid+1,right,tmp);
        if(nums[mid]//此时crossnum=0
            return leftnum+rightnum;
        }
        int crossnum=mergenum(nums, left,mid,right,tmp);
        return rightnum+leftnum+crossnum;
    }
    public int mergenum(int[] nums,int left,int mid,int right,int[]tmp){
        for(int i=left;i){
            tmp[i]=nums[i];
        }
        int i=left,j=mid+1;
        int count=0;
        for(int k=left;k){
            if(i==mid+1){//表示左边的遍历到末尾了
                nums[k]=tmp[j];
                j++;
            }else if (j==right+1){//表示右边的遍历到末尾了
                nums[k]=tmp[i];
                i++;
            }else if(tmp[i]tmp[j]){
                nums[k]=tmp[i];
                i++;
            }else{
                nums[k]=tmp[j];
                j++;
                count+=(mid-i+1);//这里需要注意不是自增1，而是要计算索引间距
            }
        }
        return count;
    }
 
}