优选算法的妙思之流：分治——归并专题

专栏：算法的魔法世界

个人主页：手握风云

目录

一、归并排序

二、例题讲解

2.1. 排序数组

2.2. 交易逆序对的总数

2.3. 计算右侧小于当前元素的个数

2.4. 翻转对

一、归并排序

        归并排序也是采用了分治的思想，将数组划分为多个长度为1的子数组进行排序，再把多个子数组合并为最终的数组。

二、例题讲解

2.1. 排序数组

        我们再来回顾一下归并排序的大体思路：以数组的中间值将数组划分为两个子数组，以此再继续划分，直至将数组划分为里面只有一个元素，就可以向上返回。当左边排完后，再去排右边，然后再将两个子数组进行合并，直到合并为原来的数组长度。

        完整代码实现：

class Solution { public int[] sortArray(int[] nums) { MergeSort(nums, 0, nums.length - 1); return nums; } private void MergeSort(int[] nums, int left, int right) { if (left >= right) return; //根据中间点划分左右子数组 int mid = (left + right) / 2; MergeSort(nums, left, mid); MergeSort(nums, mid + 1, right); //合并两个有序数组 int[] tmp = new int[right - left + 1]; int p1 = left, p2 = mid + 1, i = 0; while (p1 <= mid && p2 <= right) { tmp[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++]; } while (p1 <= mid) { tmp[i++] = nums[p1++]; } while (p2 <= right) { tmp[i++] = nums[p2++]; } //还原 for (int j = left; j <= right; j++) { nums[j] = tmp[j - left]; } }}

2.2. 交易逆序对的总数

        暴力解法，利用两层for循环，先固定其中一个数，再让其他数与这个数进行比较，如果小，就让计数器++。

class Solution { public int reversePairs(int[] record) { int count = 0; for(int i = 0;i < record.length;i ++){ for(int j = i + 1;j  record[j]) count++; } } return count; }}

        第二种解法，将数组划分为两块，先找出左区域的逆序对，再找出右区域的逆序对，最后再一左一右随机挑一个数找出逆序对。但这样的解法本质上还是一个暴力枚举。我们接着来及逆行优化，我们先找完左区域的逆序对，然后对左区域进行排序；找完右区域的逆序对，然后对右区域进行排序。我们在左右区域里面随机挑数的时候是不会影响逆序对的数量。

        当我们在左右区域里面分别寻找逆序对时，如果数组长度较大，那么我们还可以再接着划分，继续按照上面的思路来找出逆序对的总数，这个部分就可以在递归中完成，所以我们在处理一左一右时也可以排个序。

        接下来是查找子数组里面逆序对的数目，如下图所示，p1左侧是子数组中较小的元素，p2左侧也是子数组中较小的元素。我们先固定p2这个数，接下来就是在[left,p1]这段区间里面寻找比p2大的元素。如果p1所指的元素比p2所指的元素小或者等于，那么就让p1++；如果p1所指的元素比p2所指的元素大，那么p1后面的元素就都是比p2大，就可以快速的统计出数目，然后再让p2++。

        完整代码实现：

class Solution { int[] tmp; public int reversePairs(int[] record) { int n = record.length; tmp = new int[n]; return MergeSort(record, 0, n - 1); } private int MergeSort(int[] nums, int left, int right) { if (left >= right) return 0; int ret = 0; //中点元素 int mid = (left + right) / 2; //左半部分的数目+右半部分的数目 ret += MergeSort(nums, left, mid); ret += MergeSort(nums, mid + 1, right); //一左一右的数目 int p1 = left, p2 = mid + 1, i = 0; while (p1 <= mid && p2 <= right) { if (nums[p1] <= nums[p2]) { tmp[i++] = nums[p1++]; } else { ret += mid - p1 + 1; tmp[i++] = nums[p2++]; } } while (p1 <= mid) tmp[i++] = nums[p1++]; while (p2 <= right) tmp[i++] = nums[p2++]; for (int j = left; j <= right; j++) { nums[j] = tmp[j - left]; } return ret; }}

2.3. 计算右侧小于当前元素的个数

        这道题要我们求出一个数组元素右边有多少个数比它小，我们可以仿照上一题的思路，只不过这道题要把数组降序排列。

        把数组分成两部分，先找出左区域里面比自身小的个数，再找出右区域比自身小的个数，再一左一右去寻找个数。因为数组是降序排列的，所以p1、p2左边都是相对较大的元素。如果nums[p1]nums[p2]，因为我们最终是要返回一个顺序表，所以我们要用该元素对应的位置来统计结果(right-p2+1)。但是经过归并排序后，数组下标已经乱了，下一步就是要求数组元素对应的原始下标。

        我们可以使用哈希思想来解决数组下标与元素的动态绑定，如果数组里面有重复元素，使用哈希表就很难。当对数组进行排序时，数组下标也要随着变换。

        完整代码实现：

class Solution { int[] ret; int[] index;//标记原始下标 int[] tmpIndex;//用于合并时的数组 int[] tmpNum; public List countSmaller(int[] nums) { int n = nums.length; ret = new int[n]; index = new int[n]; tmpIndex = new int[n]; tmpNum = new int[n]; //初始化index数组 for (int i = 0; i < n; i++) { index[i] = i; } Mergesort(nums,0,n - 1); List res = new ArrayList(); for(int x : ret) res.add(x); return res; } private void Mergesort(int[] nums, int left, int right) { if(left >= right) return; //根据中间元素划分区间 int mid = (left + right) / 2; //处理左右区间 Mergesort(nums,left,mid); Mergesort(nums,mid + 1,right); //合并 int p1 = left,p2 = mid + 1,i = 0; while(p1 <= mid && p2 <= right){//降序 if(nums[p1] <= nums[p2]){ tmpNum[i] = nums[p2]; tmpIndex[i++] = index[p2++]; } else { ret[index[p1]] += right - p2 + 1; tmpNum[i] = nums[p1]; tmpIndex[i++] = index[p1++]; } } //处理剩余的排序 while(p1 <= mid){ tmpNum[i] = nums[p1]; tmpIndex[i++] = index[p1++]; } while(p2 <= right){ tmpNum[i] = nums[p2]; tmpIndex[i++] = index[p2++]; } for (int j = left; j <= right; j++) { nums[j] = tmpNum[j - left]; index[j] = tmpIndex[j - left]; } }}

2.4. 翻转对

        我们依然可以按照逆序对那道题，将数组划分为两块，求出左区域、右区域以及一左一右的翻转对的和。但是逆序对那道题是1:1进行比较的，而这道题需要前面的元素大于后面元素的2倍，就不能按照归并排序的思路来解决。所以我们先计算翻转对的数目，我们可以有两种思路：1.计算当前元素后面，有多少元素的2倍比该数小；2.计算当前元素后面，有多少元素的一半比该数大。

        我们先来讲下方法1（按照降序排列，没有边界）：利用数组有序的特性计算翻转对。如果nums[p1]nums[p2]时，就可以统计出数目来。如果我们让p2回退，那么时间复杂度就会达到级别。因为数组是降序的，当p1右移时，所指向的元素也会变小，没必要再让p2回退，就可以构成同向双指针了。方法2也同理，如果nums[p1]>= nums[p2]，就让p1向右移动，直到nums[p1]<nums[p2]，再让p2向右移动，p1同样不用回退。

        完整代码实现：

class Solution { int[] tmp; public int reversePairs(int[] nums) { int n = nums.length; tmp = new int[n]; return Mergesort(nums,0,n - 1); } private int Mergesort(int[] nums, int left, int right) { if(left >= right) return 0; int ret = 0; int mid = (left + right) / 2; ret += Mergesort(nums,left,mid); ret += Mergesort(nums,mid + 1,right); int p1 = left,p2 = mid + 1,i = left; while(p1 <= mid) { while (p2 = nums[p1] / 2.0) p2++; if(p2 > right) break; ret += right - p2 + 1; p1++; } p1 = left; p2 = mid + 1; while(p1 <= mid && p2 <= right){ tmp[i++] = (nums[p1] <= nums[p2]) ? nums[p2++] : nums[p1++]; } while(p1 <= mid) tmp[i++] = nums[p1++]; while(p2 <= right) tmp[i++] = nums[p2++]; for (int j = left; j <= right; j++) { nums[j] = tmp[j]; } return ret; }}