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]; } } }