常规归并排序求逆序对 leetcode LCR170
import java.util.*;
class Main {
public static void main(String []args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int n = sc.nextInt();
if(n==0){
break;
}
int [] record = new int [n];
for(int i = 0;i<n;i++){
int number = sc.nextInt();
record[i] = number;
}
reversePairs(record);
System.out.println(count);
}
}
static long count;
public static long reversePairs(int[] record) {
count = 0;
merge(record,0,record.length-1);
return count;
}
public static void merge(int [] nums,int left,int right){
int mid = left+(right-left)/2;
if(left<right){
merge(nums,left,mid);
merge(nums,mid+1,right);
mergeSort(nums,left,mid,right);
}
}
public static void mergeSort(int [] nums,int left,int mid,int right){
int [] tempArr = new int [right-left+1];
int index = 0;
int temp1 = left;
int temp2 = mid+1;
while(temp1<=mid&&temp2<=right){
if(nums[temp1]<=nums[temp2]){
tempArr[index++] = nums[temp1++];
}else{
count+=(mid-temp1+1);
tempArr[index++] = nums[temp2++];
}
}
while(temp1<=mid){
tempArr[index++] = nums[temp1++];
}
while(temp2<=right){
tempArr[index++] = nums[temp2++];
}
for(int i = 0;i<tempArr.length;i++){
nums[i+left] = tempArr[i];
}
}
}