# Reverse order pair in the [sword finger offer] array

## 1, Title Description

Two numbers in an array, if the first number is greater than the latter, then the two numbers form an inverse pair. Enter an array to find the total number of reverse pairs in the array, P. And output the result of P to 1000000007. I.e. output P% 100000007

• Enter a description

Ensure that the same number does not exist in the input array
Data range:
For data of% 50, size < = 10 ^ 4
Size < = 10 ^ 5 for data of% 75
For data of% 100, size < = 2 * 10 ^ 5

## 2, Thought analysis and code implementation

matters needing attention:
Due to the increase of the number of elements in the array, the reverse order pairs involved in the topic may exceed the value of int, so the count% 100000007 operation should be carried out in time in the calculation process, rather than wait until the last unified operation.
Method 1: Violence Law

Two for loops are nested. The whole array is scanned in sequence. Each time a number is scanned, the size relationship between the current number and the subsequent number is compared one by one. If the latter number is smaller than the other, a reverse order pair is formed.
Time complexity: O(n^2) timeout
Space complexity: O (1)

```public class Solution {
public int InversePairs(int [] array) {
int len=array.length;
if(len<=1)
return 0;
int count=0;
for(int i=0;i<len-1;i++){
for(int j=i+1;j<len;j++){
if(array[i]>array[j])
count++;
}
}
count=count%1000000007;
return count;
}
}
```

Method 2: the order of sword finger offer merging

First, divide the array into subarrays, count the number of reverse pairs in subarrays, and then count the number of reverse pairs between two adjacent subarrays. In the process of counting the logarithm of reverse order, we also need to sort the array.

• Merge sort algorithm
```  public void mergeSortCore(int[] arr, int start, int end){}
if(start>=end){
return ;
}
int mid=(end+start)/2;
mergeSortCore(arr,start,mid);
mergeSortCore(arr,mid+1,end);
merge(arr,start,mid,end);
}
public void merge(int[] arr, int start, int mid, int end){
int[] temp=new int[end-start+1]; //Auxiliary array
int i=0,p1=start,p2=mid+1;
//Ordered auxiliary array
while(p1<=mid&&p2<=end){
if(arr[p1]<=arr[p2]){
temp[i]=arr[p1];
i++;
p1++;
}else {
temp[i]=arr[p2];
i++;
p2++;
}
}
while(p1<=mid){
temp[i++]=arr[p1++];
}
while(p2<=end){
temp[i++]=arr[p2++];
}
for(int i=0;i<temp.length;i++){
arr[start+i]=temp[i];
}
}
```
• Find the reverse order to merge from tail pointer
```public class Solution {
int count=0;
public int InversePairs(int [] array) {
//Using the idea of merging and sorting to write
mergeSortCore(array,0,array.length-1);
count=count%1000000007;
return count;
}
//Merge sort
public void mergeSortCore(int[] arr, int start, int end){
if(start>=end){
return;
}
int mid=(end+start)/2;
mergeSortCore(arr,start,mid);
mergeSortCore(arr,mid+1,end);
merge(arr,start,mid,end);
}
public void merge(int[] arr, int start, int mid, int end){
int[] temp=new int[end-start+1]; //Auxiliary array
int i=end-start, p1=mid, p2=end;
//Ordered auxiliary array
while(p1>=start&&p2>mid){
if(arr[p1]>arr[p2]){
//If the front is larger than the back, there are P2 mid reverse pairs
count=(count+p2-mid)%1000000007;
temp[i]=arr[p1];
i--;
p1--;
}else {
temp[i]=arr[p2];
i--;
p2--;
}
}
while(p1>=start){
temp[i--]=arr[p1--];
}
while(p2>mid){
temp[i--]=arr[p2--];
}
for(int j=0;j<temp.length;j++){
arr[start+j]=temp[j];
}
}
}
```

Added by gregor171 on Thu, 18 Jun 2020 13:00:36 +0300