leetcode 493

秒速五厘米 2021-12-03 13:04 88阅读 0赞

//利用归并排序来完成，归并排序可参考前面代码，归并排序可用来完成这类逆序对之类的问题，采用分治的思想，对于归并排序的代码不需要多改动，只需要在归并之前进行一次寻找操作，找出count的数量

class Solution \{  
    private int count=0;  
    public int reversePairs(int\[\] nums) \{  
         if(nums == null || nums != null && nums.length == 0)  
            return 0;  
        mergeSort(nums,0,nums.length-1);  
        return count;  
    \}  
    public void mergeSort(int\[\] arr,int l,int r)  
    \{  
        if(l>=r)  
            return ;  
        int mid=(l+r)/2;  
        mergeSort(arr,l,mid);  
        mergeSort(arr,mid+1,r);  
        merge(arr,l,mid,r);  
    \}  
    public void merge(int\[\] arr,int l,int mid,int r)  
    \{  
        int\[\] aux=new int\[r-l+1\];  
        for(int i=l;i<=r;i++)  
        \{  
            aux\[i-l\]=arr\[i\];  
        \}

//这几行代码就是寻找count的操作了，可以重新写个函数来完成这部分

//本人之前的错误一直是想要在归并的时候来进行判断count的数量，也就是在后面的for循环中比较两个数的值时，比如说第一个 i 指向的那个元素与右边 j 指向的那个元素比较时，还要多判断一下是否是两倍的大小，非常不容易写，我也一直没写出来，后来参考了一下别人的归并过程才发现，这部分完全可以独立出来写  
**        int i=l,j=mid+1;**  
**        while(i<=mid&&j<=r)**  
**        \{**   
**            long x=arr\[i\];**  
**            long y=2\*(long)arr\[j\];**  
**            if(x>y)**  
**            \{**   
**                count+=mid-i+1;**  
**                j++;**  
**            \}**  
**            else\{**   
**                i++;**  
**            \}**  
**        \}**  
          
        i=l;  
        j=mid+1;  
        for(int k=l;k<=r;k++)  
        \{  
            if(i>mid)  
            \{  
                arr\[k\]=aux\[j-l\];  
                j++;  
            \}  
            else if(j>r)  
            \{  
                arr\[k\]=aux\[i-l\];  
                i++;  
            \}  
            else  if(aux\[i-l\]<aux\[j-l\])  
            \{  
                arr\[k\]=aux\[i-l\];  
                i++;  
            \}  
            else \{  
                arr\[k\]=aux\[j-l\];  
                j++;  
            \}  
        \}  
    \}  
\}

转载于:https://www.cnblogs.com/cold-windy/p/11195398.html