Reverse pairs in an array

Knowledge point Array

describe

Two numbers in an array , If the number in front is greater than the number in the back , Then these two numbers form a reverse order pair . Enter an array , Find the total number of reverse pairs in this array P. And will P Yes 1000000007 The output of the result of taking the mold . The output P mod 1000000007
Data range ：  about  50\%50%  The data of , size\leq 10^4size≤104
about  100\%100%  The data of , size\leq 10^5size≤105

The values of all numbers in the array meet  0 \le val \le 10000000≤val≤1000000

requirement ： Spatial complexity  O(n)O(n), Time complexity  O(nlogn)O(nlogn)

Input description ：

Make sure that the same number is not in the input array

         In fact, this topic feels quite difficult , At first, I had no idea . Later, I feel that this problem should be sorted in essence . There is reverse order in the array , Suppose I pass the sorting algorithm , In the sorting process, every time you exchange a large number to a small number , It shows that these two numbers are in reverse order , In this way, the number of times to exchange in the sorting process is the number of reverse pairs .

        Here is the code I tried to write , Passing rate 5/6, There is a timeout . I don't know .

// Total number of reverse pairs = The sum of the reverse pairs of numbers at each position in the array 
// Algorithm complexity O(nlogn), Then it should be a for Loop nested a binary sort 
// It feels like this is essentially a sort algorithm , Put this array in positive order according to some sort algorithm , Exchanging data every two indicates that there is a reverse order pair ？？
// Using this sort algorithm , Pass rate is 5/6,  And prompt that your program fails to run within the specified time , Please check whether the loop is wrong or the algorithm is too complex .
int length = array.length;
int deOrderNum = 0; // Count the number of pairs in reverse order 
for (int i = 1; i < length; i++) {
    for (int j = i; j>0 && (array[j-1] - array[j]) > 0 ; j--) {
        int temp = array[j];
        array[j] = array[j - 1];
        array[j - 1] = temp;
        deOrderNum = (deOrderNum + 1) % mod;
    }
}
return deOrderNum % 1000000007;

        Read the writing of the great God , It is made by merging and sorting , It seems that my direction is right , This problem is essentially a sort .

You need to learn the algorithm of merging and sorting . Here I try to write one after looking at the algorithm evolution diagram . The algorithm evolution diagram is as follows

  You can see , The idea of the algorithm is “ Split first , Re orderly merger ”

1、 Split the large array into two sub arrays , And the subarray is recursively split down , Until the last subarray length is 1;

2、 Set the length of the array to 1 The length of the array of and adjacent arrays is 1 The subarrays of are combined into an ordered parent array , Then recursively combine into a larger array , Until the length of the array is equal to the length of the original array .

Code implementation ( Didn't write , It's embarrassing )

         I can't write it, so I went to see the writing method of online merging and sorting , It's not that hard to find , But when I write, I feel very difficult , Ah , Oneself is rubbish .

        Write directly on the Internet （ Reference article “Java Basics —— Recursive implementation of merge sort and quick sort ”）

Algorithm description ：

• Put the length to n The input sequence of is divided into two lengths n/2 The subsequence ;

• Merge and sort these two subsequences respectively ;

• Merge two sorted subsequences into a final sorted sequence .

Recursive understanding ：

        Sort the entire array Can be broken down into Sort the left sub array of the array , Then sort the right sub array of the array , Then string the left and right sub arrays into an array and arrange them in order . If you use a function f(array) Represents the function that meets our sorting requirements , be

f(array)=merge(f(array[0~mid]）+ f(array[mid + 1]~lenght - 1))

Because the left and right subarrays still need to be merged , So suppose there is such a function merge().

Code implementation

/**
 *  Break up the array 
 * @param array
 * @param left
 * @param right
 */
public static void mergeSort(int array[],int left,int right){
    if(left>=right){
        return;
    }
    int mid = (left+right)>>>1;
    mergeSort(array,left,mid);
    mergeSort(array,mid+1,right);
    merge(array,left,mid,right);// Merge 
}


/**
 *  Merge array 
 * @param array
 * @param left
 * @param mid
 * @param right
 */
public static void merge(int[] array,int left,int mid,int right){
    int s1 = left;
    int s2 = mid+1;
    int [] res = new int[right-left+1];
    int i=0;
    while(s1 <= mid && right >=s2){
        if(array[s1] <= array[s2]){
            res[i++] = array[s1++];
        }else {
            res[i++] = array[s2++];
        }
        //res[i++]= array[s1] <= array[s2] ? array[s1++] :array[s2++];
    }
    while(s1 <= mid){
        res[i++] = array[s1++];
    }
    while(s2 <= right){
        res[i++] = array[s2++];
    }
    System.arraycopy(res,0,array,0+left,res.length);
}

1、mergeSort Recursive function first sets the end condition of recursion , And the condition must be at the top of the function if(left>=right);

2、 I was trying to write a recursive implementation , Thinking mergeSort What should be returned , How to set parameters ？ In fact, array parameters are addressed , So there is no need for the function to return an array , Just make sure that after calling the function array Just order the elements in ; Tried mergeSort There is only one parameter representing the array , But I find it inconvenient , If I want to get the left or right sub array of the array , I also need to save the left and right subarrays with a temporary array .

3、 Merge recursion is not tail recursion like binary search , After calling your own function, there is logic to be executed .

Great God writing reference article https://github.com/Damaer/CodeSolution/blob/main/%E5%89%91%E6%8C%87Offer/%E5%89%91%E6%8C%87Offer35-%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E9%80%86%E5%BA%8F%E5%AF%B9.md