剑指offer--数组中的逆序对

红太狼 2021-09-27 09:22 294阅读 0赞

问题描述：  
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007  
输入描述:  
题目保证输入的数组中没有的相同的数字

数据范围：

对于%50的数据,size<=10^4
    
    对于%75的数据,size<=10^5
    
    对于%100的数据,size<=2*10^5

解题思路：  
1.采用归并排序的思想  
2.合并时，增加若左边的数R\[i\]大于右边的数R\[j\]，由于数据已经有序，说明i右边的所有数大于R\[j\]。

public class Solution {
        private static int sum = 0 ;
        private static int mod = 1000000007 ;
        public static void main(String args[]){
            Solution a = new Solution();
            int[] array = new int[]{
       7,5,6,4};
            a.InversePairs(array);
            System.out.println(sum);
        }
        public int InversePairs(int [] array) {
            if(array == null || array.length <= 1){
                return 0 ;
            }
            int len = array.length;
            cal(array,0,len-1);
            return sum ;
        }
    
        private void cal(int[] array,int left, int right) {
            if(left < right ){
                int q = (left+right)/2;
                cal(array,left,q);
                cal(array,q+1,right);
                merge(array,left,q,right) ;
            }
        }
    
        private void merge(int[] array, int left, int q, int right) {
            int len1 = q+1-left;
            int len2 = right - q;
            int[] L = new int[len1+1];
            int[] R = new int[len2+1];
            for(int i = 0 ;i<len1 ;i++){
                L[i] = array[left+i];
            }
            L[len1] = Integer.MAX_VALUE;
            for(int i = 0 ;i<len2 ;i++){
                R[i] = array[q+1+i];
            }
            R[len2] = Integer.MAX_VALUE;
            int i = 0 , j = 0 ;
            for(int k = left ;k<=right ; k++){
                if(L[i] <= R[j]){
                    array[k] = L[i++];
                }else {
                    if(i!=len1){
                        sum = (sum + len1 - i ) % mod ;
                    }
                    array[k] = R[j++];
                }
            }
        }
    }