在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
记录一下归并排序的做法。思路就是在归并的时候记录逆序对。由于在归并的时候左右两个数组都已经升序排号，因此在对右边数组进行归并的时候，左边数组的元素都大于该元素，记录此时左边数组元素的个数即可。
直接在归并排序进行操作，增加方法的返回值即可。
我要评论class Solution {
public int reversePairs(int[] nums) {
if(nums==null||nums.length<=1) return 0;
return mergesort(nums,0,nums.length-1);
}
public int mergesort(int[] nums,int left,int right){
if(left>=right) return 0;
int mid=(left+right)>>>1;
int leftcount=mergesort(nums,left,mid);
int rightcount=mergesort(nums,mid+1,right);
int crosscount=merge(nums,left,right,mid);
return leftcount+rightcount+crosscount;
}
public int merge(int[] nums,int left,int right,int mid){
int count=0;
int i=left;
int j=mid+1;
int k=0;
int[] tmp=new int[right-left+1];
while(i<=mid&&j<=right){
if(nums[i]<=nums[j]){
tmp[k++]=nums[i++];
}
else{
tmp[k++]=nums[j++];
count+=mid-i+1;
}
}
while(i<=mid){
tmp[k++]=nums[i++];
}
while(j<=right){
tmp[k++]=nums[j++];
}
for(int ii=0;ii<tmp.length;ii++){
nums[left+ii]=tmp[ii];
}
return count;
}
}
本文地址：https://blog.csdn.net/qq_44837971/article/details/107286975
如对本文有疑问， 点击进行留言回复！！
springboot利用profile配置文件进行多环境切换
如何使用MyBatis-Plus代码生成器(逆向工程)一键生成代码
网友评论