在做力扣的第51题数组的逆序对时，当时我首先想到的是暴利求解，但是暴利求解在这道题中不能使用，因为力扣会给大量的数据，暴利求解很耗时，因此不能够使用。然后就研究了归并算法的解题思路，首先就是先将数组进行拆分，拆成左右两组数据，然后每组数据在进行拆分，直到剩余一个数据的时候进行，两两排序。下边就套算法吧！
public class Solution {
static int count = 0;
public int ReversePairs(int[] nums) {
sort(nums,0,nums.Length-1);
return count;
}
//进行递归
public static void sort(int[] nums,int L, int R){
if(L>=R){
return;
}
int mid = L+((R-L)>>1);
sort(nums, L, mid);
sort(nums, mid+1, R);
merge(nums,L,mid,R);
}
//进行数组合并
public static void merge(int[] nums,int L,int Mid, int R){
int[] temp = new int[R-L+1];
int i =0;
int p1 = L;
int p2 = Mid+1;
while(p1<=Mid && p2<=R){
//当左边大于右边的时候，说明在后边，让count++
if(nums[p1]>=nums[p2]){
//左边如果等于右边，让count--
for (int j = p1; j < Mid + 1; j++) {
if (nums[j] == nums[p2]){
count--;
continue;
}
break;
}
if ((Mid + 1 - p1) >= 0) {
count = count + Mid + 1 - p1;
}
}
temp[i++] = nums[p1]<nums[p2]?nums[p1++]:nums[p2++];
}
while(p1<=Mid){
temp[i++] = nums[p1++];
}
while(p2<=R){
temp[i++] = nums[p2++];
}
for(i=0;i<temp.Length;i++){
nums[L+i] = temp[i];
}
}
}
网友评论