温州网页模板建站,诚信通网站怎么做,wordpress 登录 api,个人免费网站建站排名描述 解题思路#xff1a;归并排序 分治#xff1a;分治即“分而治之”#xff0c;“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题#xff0c;子问题继续按照这样划分#xff0c;直到问题可以被轻易解决#xff1b;“治”指的是将子问题单独进…描述 解题思路归并排序 分治分治即“分而治之”“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题子问题继续按照这样划分直到问题可以被轻易解决“治”指的是将子问题单独进行处理。经过分治后的子问题需要将解进行合并才能得到原问题的解因此整个分治过程经常用递归来实现。
具体做法 1、这里要借助一个辅助数组用来暂时存储合并后的结果。然后就开始进入划分阶段把原数组从中间分开直到子数组长度为1。 2、使用归并排序对原数组进行排序并且统计逆序对在这里设置两个指针i,j分别在左右子区间上移动此时左区间的下标i都是小于右区间的若知道了第一个大于a[j]的数设为a[i],则左区间中a[i]以后的所有数都比a[j]大。故此时在左区间中与a[j]构成逆序对的数字个数为左边剩下的数剩余的数右端-左端1mid-i1。这个就是逆序对的计算方法。 3、将排好序的子序列合并同时累加逆序对。
图解
代码
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param nums int整型一维数组 * return int整型*/public int mod 1000000007;public int mergeSort(int left,int right,int [] data,int[] temp){if(leftright){return 0;}int mid (leftright)/2;int res mergeSort(left,mid,data,temp)mergeSort(mid1,right,data,temp);res % mod;//i,j代表两个指针分别在左右子区间上移动。int i left,j mid1;for(int kleft;kright;k){temp[k] data[k]; //temp为辅助数组}for(int kleft;kright;k){if(imid1){ //如果左边有剩余不太懂这处代码data[k] temp[j];}//如果右边有剩余或者左边数更小else if(jright1||temp[i]temp[j]){ data[k] temp[i];//不太懂处代码}else{data[k] temp[j];//逆序对计算方法res mid-i1;}}return res%mod;}public int InversePairs (int[] nums) {// write code hereint n nums.length;int [] res new int[n];return mergeSort(0,n-1,nums,res);}
}个人疑问不知道有没有和我一样的小伙伴在看这道题的解题思路会有这样的疑问为什么可以排序呢这里题目要求的是在一个已经列好的数组中左边的数大于右边才被称为逆序数而如果使用归并排序的话这个数组不是都有序了吗有序的基础上找逆序不是和题目违背了吗
经过思考我个人的见解是这样的这里归并排序计算逆序对的数量和暴力解法不一样暴力解法是在一个已有的数组中对于每一个数都判断其他的数是否比该数大而递归排序它比较的不是相邻的两个数而是相邻的两个子数组我认为这是看懂这道题的关键因为比较的是两个子数组所以在两个子数组中已经排好序是没关系的因为两个子数组的相对顺序没有变所以如果在左区间发现了一个比右区间大的数那么说明左区间中这个数以后的数都会比右区间大这是递归算法计算的公式。
