归并排序运用——逆序对

逆序对

假设升序为默认的序列&＃xff0c;在一个数组中&＃xff0c;数组的任意一对数字逆序即inum[j],则称这一数对为逆序数对

题目

给定一个数组&＃xff0c;求该数组的逆序数对

数组中的逆序对

示例&＃xff1a;

输入&＃xff1a;
7 5 6 4
5


思路

第一想法是暴力求解&＃xff0c;暴力的时间复杂度是O(n^2)&＃xff0c;会超时

采用归并排序来优化时间复杂度

归并排序是通过将数组分治&＃xff0c;再将两个有序数组合并&＃xff0c;那么在有序数组合并的时候就可以展开操作了&＃xff0c;具体怎么做呢&＃xff1f;

假设两个有序的数组&＃xff1a;3 5 7 9 | 2 4 6 8第一步合并&＃xff1a;
2 3 5 7 9 | 4 6 8操作开始&＃xff1a;当插入2的时候&＃xff0c;可以肯定的是2小于[3 5 7 9]中的任何一个数字
那么2的逆序数对就有4个&＃xff0c;结果&＃43;4第二步合并
2 3 5 7 9 | 4 6 8操作开始&＃xff1a;当插入3的时候&＃xff0c;可以肯定的是3小于[4 5 6]中的任何一个数字
而5 7 9 的位置也在3后面&＃xff0c;所以逆序对数为0.结果不变第三步合并
2 3 45 7 9 | 6 8操作开始&＃xff1a;当插入2的时候&＃xff0c;可以肯定的是4小于[5 7 9]中的任何一个数字
那么2的逆序数对就有3个&＃xff0c;结果&＃43;3
。
。
。
结果&＃xff1a;
2 3 4 5 6 7 8 9
这时候数组有序了&＃xff0c;逆序对数是10这时候在将 2 3 4 5 6 7 8 9和另一个数组1 2 3 4 5 6 7 8 9合并
遵循上面的操作&＃xff0c;得出 逆序对数结果 &＃43; 10 &＃43; 1 2 3 4 5 6 7 8 9]的逆序对结果0
就是两个数组合并后数组的逆序对数
ps&＃xff08;3 5 7 9 和 2 4 6 8的逆序对数均为0&＃xff09;

示例代码

class Solution {public int reversePairs(int[] nums) {
int len &＃61; nums.length;if(len<2){return 0;}int[] temp &＃61; new int[len];return mergeSort(0 , len-1 , temp , nums);}private int mergeSort(int left, int right, int[] temp, int[] nums) {if(left&＃61;&＃61;right){return 0;}int mid &＃61; left&＃43;(right-left)/2;int left_ans &＃61; mergeSort(left , mid , temp , nums);int right_ans &＃61; mergeSort(mid&＃43;1 , right , temp , nums);int merge_ans &＃61; mergeArray(left , mid , right , temp ,nums);return left_ans&＃43;right_ans&＃43;merge_ans; //左数组的逆序对数&＃43;合并计算的逆序对数&＃43;右数组的逆序对数}private int mergeArray(int left, int mid, int right, int[] temp, int[] nums) {int count &＃61; 0;System.arraycopy(nums , 0 , temp , 0 , nums.length);int i &＃61; left;int j &＃61; mid&＃43;1;for (int k &＃61; left; k <&＃61;right ; k&＃43;&＃43;) {if(i&＃61;&＃61;mid&＃43;1){nums[k]&＃61;temp[j];j&＃43;&＃43;;}else if(j&＃61;&＃61;right&＃43;1){nums[k] &＃61; temp[i];i&＃43;&＃43;;}else if(temp[i]<&＃61;temp[j]){nums[k] &＃61; temp[i];i&＃43;&＃43;;}else {nums[k] &＃61; temp[j];j&＃43;&＃43;;count&＃43;&＃61;(mid-i&＃43;1); //最重要的计数操作}}return count;}
}


类似题目

• 翻转对
• 区间和的个数