使用成员变量记录逆序对总数
数组中的逆序对
http://www.nowcoder.com/questionTerminal/96bd6684e04a44eb80e6a68efc0ec6c5
全称都是归并排序的,只是在逆序的情况下(nums[start1]>nums[start2]),需要增加更新逆序对的代码。
很简单,使用成员变量记录逆序对总数。
private int pairs. ... if(nums[start1]>nums[start2]){ ... pairs+=mid-start1+1; pairs%=10000007; } ...
/** * 在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。 * 输入一个数组,求出这个数组中的逆序对的总数P。 * 并将P对1000000007取模的结果输出。 即输出P%1000000007 * @param array 数组 * @return 数组中的逆序对的总数P */ public int InversePairs(int [] array) { if(array==null||array.length<2){ return 0; } int[] aux=new int[array.length]; InversePairs(array,aux,0,array.length-1); return this.pairs; } private int pairs; public void InversePairs(int[] nums,int[]aux,int left,int right){ if(left<right){ int mid=left+(right-left)/2; InversePairs(nums,aux,left,mid); InversePairs(nums,aux,mid+1,right); merge(nums,aux,left,mid,right); } } public void merge(int[] nums,int[] aux,int left,int mid,int right) { //标准的merge过程,当逆序时,格式为mid-i+1,相当于(mid与i之间的数量) int start1 = left, end1 = mid, start2 = mid + 1, end2 = right; int k = left; while (start1 <= end1 && start2 <= end2) { //存在逆序对 if (nums[start1] > nums[start2]) { aux[k++] = nums[start2++]; this.pairs += (mid - start1 + 1); this.pairs %= 1000000007; } else { aux[k++] = nums[start1++]; } } while (start1 <= end1) { aux[k++] = nums[start1++]; } while (start2 <= end2) { aux[k++] = nums[start2++]; } for (int i = left; i <= right; i++) { nums[i] = aux[i]; } }