【算法专场】分治（下）

前言

在算法专栏上一篇，我们讲解了分治是什么，如何利用分治的思想来解决一些排序问题或者找指定元素，而在上篇中，我们主要讲的是利用快排，那么本篇我们就来讲解一下归并排序。

归并排序在我数据结构专栏中有涉及，想要了解的更详细的可以去观看。

归并排序

思想

归并排序也是利用了分治的思想，将一个序列化成一个个子序列，在每个子序列上进行排序，再将已经排好的子序列进行合并，就能得到一个有序的序列。

归并排序和快速排序虽然都是利用了分治的思想，但两者排序的时机不同：

快速排序是在序列分割成一个个子序列的过程同时对子序列进行排序的；

而归并排序则是将序列分成一个个子序列之后，在序列合并前进行排序。

简单来说：快排是在分割时就进行排序，归并则是在合并的过程中进行排序。

912. 排序数组

这道题虽然在上一篇中已经讲过，但使用的是快排解决，本篇我们就用归并来解决这道题。

算法思路

这里我们采用归并的递归方法来解决。

辅助数组：辅助数组主要是为了存储已经排好序的数组。
创建归并函数：我们需要三个参数，分别是数组、每次递归的左边界left、右边界right。当left>=right时，说明数组已经排完序，此时可以直接返回。若还没有排完序，我们需要对数组进行分割排序。当分割完成后，我们就可以借助辅助数组，对数组进行排序。

算法代码


public class Solution {// 临时数组，用于归并排序时暂时存储元素int[] tmp;/*** 对数组进行排序** @param nums 待排序的数组* @return 排序后的数组*/public int[] sortArray(int[] nums) {// 初始化临时数组tmp = new int[nums.length];// 调用归并排序mergeSort(nums, 0, nums.length - 1);return nums;}/*** 归并排序算法** @param nums 待排序的数组* @param left 排序数组的起始位置* @param right 排序数组的结束位置*/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 i = left, j = mid + 1;int cnt = 0;// 合并左右两部分数组while (i <= mid && j <= right) {// 将较小的元素放入临时数组if (nums[i] < nums[j]) {tmp[cnt++] = nums[i++];} else {tmp[cnt++] = nums[j++];}}// 处理左半部分剩余的元素while (i <= mid) {tmp[cnt++] = nums[i++];}// 处理右半部分剩余的元素while (j <= right) {tmp[cnt++] = nums[j++];}// 将排序后的元素从临时数组复制回原数组for (int k = left; k <= right; k++) {nums[k] = tmp[k - left];}}
}

时间复杂度为O(n*logn),空间复杂度为O(n).

LCR 170. 交易逆序对的总数

算法思路

这道题其实也是可以用归并排序来解决，在我们归并排序合并左右数组的时候，如果左区间（在合并的时候，左右数组已经是有序的了）中的元素大于右区间的元素，那么此时我们就可以知道逆序对有【mid-left+1】对。

示例：（画的有点抽象）

算法代码


public class Solution {// 计数器，用于统计逆序对的总数int count=0;// 临时数组，用于归并排序时暂存数据int[] tmp;/*** 计算逆序对的总数** @param record 输入的数组* @return 逆序对的总数*/public int reversePairs(int[] record) {// 初始化临时数组tmp=new int[record.length];// 调用归并排序mergeSort(record,0,record.length-1);// 返回逆序对的总数return count;}/*** 归并排序算法** @param nums 待排序的数组* @param left 排序数组的起始位置* @param right 排序数组的结束位置*/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 i = left, j = mid + 1;int cnt = 0;// 合并左右两部分数组while (i <= mid && j <= right) {// 将较小的元素放入临时数组if (nums[i] < nums[j]) {tmp[cnt++] = nums[i++];} else {// 当右半部分的元素小于左半部分的元素时，说明找到了逆序对count+=mid-i+1;tmp[cnt++] = nums[j++];}}// 处理左半部分剩余的元素while (i <= mid) {tmp[cnt++] = nums[i++];}// 处理右半部分剩余的元素while (j <= right) {tmp[cnt++] = nums[j++];}// 将排序后的元素从临时数组复制回原数组for (int k = left; k <= right; k++) {nums[k] = tmp[k - left];}}
}

时间复杂度为O(n*logn),空间复杂度为O(n).

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

算法思路

这道题是要求每个元素后面有多个比当前元素少的个数，我们可以用归并排序来解决，在归并的时候进行计数。

1. 初始化：

我们定义四个数组ret、index、tmpNums、tmpIndex。ret数组用于存储原数组每个元素右侧小于当前元素的个数；index用来存储原始数组元素的下标；tmpNums用于存储归并排序完的元素，而tmpIndex则是存储排序完每个元素对应的原始下标位置。

2. 归并和计数：

定义一个merge方法，不需要返回值。在merge方法中，需要nums，数组的左右边界left、right；
如果left>=right时或者子数组的长度只有1时，则直接返回，此时不需要进行计数。
如果left<right，那么就将数组分割成两部分，继续调用merge方法进行递归；在合并左右两个子数组的时候，我们需要借助两个指针cur1和cur2，cur1和cur2指向左子数组和右子数组的起始位置，用一个i当做临时数组的下标。
在循环whlie(cur1<=mid&&cur2<=right)中，比价左子数组和右子数组的元素：
1. 如果nums[cur1]<=nums[cur2],将右子数组的当前元素放入到临时数组中，同时将对应的下标放入到tmpIndex中，再将i和cur2往后移；
2. 如果nums[cur1]>nums[cur2]，由于我们这里对数组是进行降序操作，所以说明从[cur2,right]这个区间上所有元素都是小于nums[cur1]的，即nums[cur1]右侧有right-cur2+1个元素小于它，将这个数量累加到ret[index[cur1]]中。再将nums[cur1]放入到临时数组tmpNums中，同时将对应的原始下标放入到tmpIndex中，再将i和cur1往后移。
当跳出循环后，说明左右子数组中其中有一个全部放入到临时数组中，但其中还有一个子数组没有放入临时数组中，我们利用两个循环来处理左子数组和右子数组的剩余元素。
当把数组全部放到临时数组后，我们再将临时数组中的元素复制回nums和index数组中。

算法代码

 int[] ret;//用来存放结果int[] index;//用来存放原始数组的下标int[] tmpNums;//辅助数组，用来存储排序后的数组int[] tmpIndex;//辅助数组，用来存储排序后的数组的下标public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpNums = new int[n];tmpIndex = new int[n];for(int i=0;i<n;i++){index[i]=i;}merge(nums,0,n-1);List<Integer> list = new ArrayList<>();for(int num:ret){list.add(num);}return list;}private void merge(int[] nums,int left,int right){if(left>=right) return;int mid = left+(right-left)/2;merge(nums,left,mid);merge(nums,mid+1,right);int cur1=left,cur2=mid+1,i=0;while (cur1<=mid && cur2<=right){if(nums[cur1]<=nums[cur2]){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}else{ret[index[cur1]]+=right-cur2+1;tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}}while (cur1<=mid){tmpNums[i]=nums[cur1];tmpIndex[i++]=index[cur1++];}while (cur2<=right){tmpNums[i]=nums[cur2];tmpIndex[i++]=index[cur2++];}for(i=left;i<=right;i++){nums[i]=tmpNums[i-left];index[i]=tmpIndex[i-left];}}

时间复杂度为(nlogn），空间复杂度为O（n）

493. 翻转对

算法思路

本道题可以用归并的方法来解决，题目要求我们找翻转对，即满足i<j，并且nums[i[>2*nums[j]。

我们可以想成nums[i]元素/2.0后，比nums[j]还要大，这样的话，我们采用归并降序就好解多了。

初始化:定义一个临时数组tmp,以及一个变量ans，用来存储翻转对的个数；
归并：
1. 定义一个merge方法，在此方法中，如果left>=right,那么就直接返回
2. 如果left<right,那么就继续对数组进行分割为两部分递归调用merge方法。
3. 定义三个变量cur1、cur2、index,cur1和cur2分别指向左右子数组的起始位置。index用做临时数组的下标
计算翻转对数量：
1. 在循环while(cur1<=mid)中，让左数组中的元素nums[cur1]，和右子数组中每个元素nums[cur2]进行比较，查看满足条件nums[cur1]/2.0<=nums[cur2]的位置，如果找到，说明从cur2到right这段区间上的元素都能和nums[cur1]构成翻转对。将right-cur2+1累加到ans中，再让cur1++，查找下一个左子数组元素的翻转对。
合并两个有序的子数组：套路和上一题差不多，都是类似写法

算法代码

// 临时数组，用于归并排序时的合并操作
int[] tmp;
// 记录翻转对的数量
int ans;/*** 计算数组中的翻转对数量。翻转对定义为：对于下标 i < j，如果 nums[i] > 2 * nums[j]，则 (i, j) 是一个翻转对。** @param nums 输入的整数数组* @return 翻转对的数量*/
public int reversePairs(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return ans;
}/*** 使用归并排序的方法对数组进行排序，并在排序过程中统计翻转对的数量。** @param nums 需要排序的数组* @param left 当前子数组的左边界* @param right 当前子数组的右边界*/
public 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 cur1 = left, cur2 = mid + 1;while (cur1 <= mid) {while (cur2 <= right && nums[cur1] / 2.0 <= nums[cur2]) cur2++;if (cur2 > right) break;ans += right - cur2 + 1;cur1++;}// 合并左右两个已排序的子数组cur1 = left;cur2 = mid + 1;int index = left;while (cur1 <= mid && cur2 <= right) {tmp[index++] = nums[cur1] <= nums[cur2] ? nums[cur2++] : nums[cur1++];}while (cur1 <= mid) tmp[index++] = nums[cur1++];while (cur2 <= right) tmp[index++] = nums[cur2++];for (int i = left; i <= right; i++) nums[i] = tmp[i];
}

时间复杂度为O(n*logN),空间复杂度为O(n)