【算法】【优选算法】分治（下）
目录
一、归并排序
题目链接：归并排序
题目描述：
题目解析：
- 就是排序数组。
解题思路：
- 分：将数组⼀分为⼆为两部分，⼀直分解到数组的⻓度为1 ，使整个数组的排序过程被分为「左半部分排序」+「右半部分排序」；
- 治：将两个较短的「有序数组合并成⼀个⻓的有序数组」，⼀直合并到最初的⻓度。
解题代码：
//时间复杂度：O(NlogN)//空间复杂度：O(n)classSolution{int[] tmp;publicint[]sortArray(int[] nums){ tmp =newint[nums.length];mergeSort(nums,0,nums.length-1);return nums;}//归并排序publicvoidmergeSort(int[] nums,int l,int r){if(l >= r)return;int left = l;int right = r;int mid =(left + right)/2;//分mergeSort(nums, l, mid);mergeSort(nums, mid+1, r);//治：合并两个有序数组int cur1 = left;int cur2 = mid +1;int i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur1]< nums[cur2]) tmp[i++]= nums[cur1++];else tmp[i++]= nums[cur2++];}while(cur1 <= mid) tmp[i++]= nums[cur1++];while(cur2 <= right) tmp[i++]= nums[cur2++];//还原for(int j = left; j <= right; j++){ nums[j]= tmp[j];}}}二、LCR170.交易逆序对的总数
题目链接：LCR170.交易逆序对的总数
题目描述：
题目解析：
- 逆序对：逆序对就是指，在该数组元素之后与比它小的元素组成的两个数字，就称为一个逆序对，返回数组中逆序对总数。
2.1 分治思想
解题思路：
- 两段子数组的逆序对和，我们可以通过递归实现。
- 那么我们的核心就是求一左一右选取逆序对的和。
- 直接去遍历求解，复杂度还是高，如果我们将两段子数组排序，那么我们就有两种方式简单求了。
- 看上面的就是与归并排序的逻辑一摸一样的。
降序排序：我们就找后一个数组中小的元素个数即可（就当nums[ cur2 ] < nums[ cur1 ]时统计即可），即[ mid+1 , right ]。如果求前一个数组大元素，会有重复。
升序排序：我们就找前一个子数组中大的元素个数即可（就当nums[ cur2 ] < nums[ cur1 ]时统计即可），即[cur1 , mid]。如果求后一个数组小元素，会有重复。
其实我们可以将数组分为两段，那么数组的总逆序对和等于：两段子数组的逆序对和 + 前面一段数组中每个元素在后面一段元素组成的逆序对和（就是遍历前面一段数组，在后面一段数组中找比该元素小的元素个数）（简称为一左一右选逆序对）。
解题代码：
//时间复杂度：O(NlogN)//空间复杂度：O(n)//升序版本：classSolution{int[] tmp;publicintreversePairs(int[] nums){int n = nums.length; tmp =newint[n];returnmerageSort(nums,0, n-1);}publicintmerageSort(int[] nums,int left,int right){if(left >= right)return0;int ret =0;int mid =(left + right)/2;//分:两段子数组的逆序对和 ret +=merageSort(nums, left, mid); ret +=merageSort(nums, mid +1, right);//治：合并两个有序数组 + 统计一左一右逆序对个数int cur1 = left, cur2 = mid +1;int i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur1]<= nums[cur2]) tmp[i++]= nums[cur1++];else{ ret +=(mid - cur1 +1); tmp[i++]= nums[cur2++];}}while(cur1 <= mid) tmp[i++]= nums[cur1++];while(cur2 <= right) tmp[i++]= nums[cur2++];//还原for(int j = left; j <= right; j++) nums[j]= tmp[j];return ret;}}//时间复杂度：O(NlogN)//空间复杂度：O(n)//降序版本：classSolution{int[] tmp;publicintreversePairs(int[] nums){int n = nums.length; tmp =newint[n];returnmerageSort(nums,0, n-1);}publicintmerageSort(int[] nums,int left,int right){if(left >= right)return0;int ret =0;int mid =(left + right)/2;//分:两段子数组的逆序对和 ret +=merageSort(nums, left, mid); ret +=merageSort(nums, mid +1, right);//治：合并两个有序数组 + 统计一左一右逆序对个数int cur1 = left, cur2 = mid +1;int i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur1]<= nums[cur2]) tmp[i++]= nums[cur2++];else{ ret +=(right - cur2 +1); tmp[i++]= nums[cur1++];}}while(cur1 <= mid) tmp[i++]= nums[cur1++];while(cur2 <= right) tmp[i++]= nums[cur2++];//还原for(int j = left; j <= right; j++) nums[j]= tmp[j];return ret;}}2.2 暴力枚举
解题思路：
- 直接两个for循环，将第一层遍历数组，第二层遍历后续元素比该元素小的数组个数。
- 会超时。
解题代码：
//时间复杂度：O(n^2)//空间复杂度：O(1)classSolution{publicintreversePairs(int[] record){int ret =0;for(int i =0; i < record.length; i++){for(int j = i +1; j < record.length; j++){if(record[i]> record[j]) ret++;}}return ret;}}三、315.计算右侧⼩于当前元素的个数
题目链接：315.计算右侧⼩于当前元素的个数
题目描述：
题目解析：
- 这道题其实跟上一题是差不多的，但是这个是记录下当前元素后面比它小的元素的个数，并存在一个数组的下标相同的位置。
- 最后返回存个数的数组。
3.1 分治思想
解题思路：
- 这道题跟上一道的解题思路是一模一样的，将数组分为两段。每个下标的数组的对应值等于：前一段个数+后一段个数。
- 由于求小的个数，所以我们使用降序求法，使用升序需要考虑边界情况。
- 当nums[ cur2 ] < nums[ cur1 ]时统计[ mid+1 , right ]个数，放入结果数组的nums[ cur1 ]对应下标位置即可。
- 我们要将数组中的值与其下标对应，由于数组中元素可以重复，所以不能使用哈希表，我们再使用一个数组记录每个元素的下标，两个数组绑定，同时移动。
- 下标数组的移动和原数组的移动是一模一样的，所以合并是也需要引入临时数组。
解题代码：
//时间复杂度：O(NlogN)//空间复杂度：O(n)//降序版本：classSolution{int[] tmpNums;int[] tmpIndex;int[] ret;int[] index;publicList<Integer>countSmaller(int[] nums){int n = nums.length; tmpIndex =newint[n]; tmpNums =newint[n]; ret =newint[n];//下标数组 index =newint[n];for(int i =0; i < n; i++) index[i]= i;mergeSort(nums,0, n-1);List<Integer> list =newArrayList<>();for(int x : ret) list.add(x);return list;}publicvoidmergeSort(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;int i = left;while(cur1 <= mid && cur2 <= right){if(nums[cur2]>= nums[cur1]){ 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(int j = left; j <= right; j++){ nums[j]= tmpNums[j]; index[j]= tmpIndex[j];}}}3.2 暴力枚举
解题思路：
- 两层for循环即可
- 会超时
解题代码：
//时间复杂度：O(n^2)//空间复杂度：O(1)classSolution{publicList<Integer>countSmaller(int[] nums){List<Integer> ret =newArrayList<>();for(int i =0; i < nums.length; i++){int a =0;for(int j = i +1; j < nums.length; j++){if(nums[j]< nums[i]) a++;} ret.add(a);}return ret;}}四、493.翻转对
题目链接：493.翻转对
题目描述：
题目解析：
- 题目非常清晰，并不用解析。
4.1 分治思想
解题思路：
- 我们依旧是将数组分为两段：那么数组的总翻转对和等于：两段子数组的翻转对和 + 前面一段数组中每个元素在后面一段元素组成的翻转对和（就是遍历前面一段数组，在后面一段数组中找比该元素一半小的元素个数）（简称为一左一右选翻转对）。
- 依旧可以是分升序和降序来求：
- 升序排序：立足cur2，我们就找前一个子数组中大的元素个数即可，即[cur1 , mid]。
- 降序排序：立足cur1，我们就找后一个数组中小的元素个数即可，即[ mid+1 , right ]。
- 但是由于我们的判断条件与合并是不一样的，所以单独写一个循环来计算。
- 每个元素不会超出int范围，但是乘2就有可能会超出，所以判断条件写
nums[cur1] / 2.0 <= nums[cur2]
解题代码：
//时间复杂度：O(NlogN)//空间复杂度：O(n)//升序版本：classSolution{int[] tmp;publicintreversePairs(int[] nums){ tmp =newint[nums.length];returnmergeSort(nums,0,nums.length-1);}publicintmergeSort(int[] nums,int left,int right){if(left >= right)return0;int mid =(left + right)/2;int ret =0;//分:两段子数组的翻转对和 ret +=mergeSort(nums, left, mid); ret +=mergeSort(nums, mid+1, right);//统计一左一右逆序对个数int cur1 = left, cur2 = mid +1;int i = left;while(cur2 <= right){while(cur1 <= mid && nums[cur1]/2.0<= nums[cur2]) cur1++;if(cur1 > mid)break; ret +=(mid - cur1 +1); cur2++;}//治：合并两个有序数组 cur1 = left; cur2 = mid +1;while(cur1 <= mid && cur2 <= right){if(nums[cur1]< nums[cur2]) tmp[i++]= nums[cur1++];else tmp[i++]= nums[cur2++];}while(cur1 <= mid) tmp[i++]= nums[cur1++];while(cur2 <= right) tmp[i++]= nums[cur2++];//还原for(int j = left; j <= right; j++){ nums[j]= tmp[j];}return ret;}}//时间复杂度：O(NlogN)//空间复杂度：O(n)//降序版本：classSolution{int[] tmp;publicintreversePairs(int[] nums){ tmp =newint[nums.length];returnmergeSort(nums,0,nums.length-1);}publicintmergeSort(int[] nums,int left,int right){if(left >= right)return0;int mid =(left + right)/2;int ret =0;//分:两段子数组的翻转对和 ret +=mergeSort(nums, left, mid); ret +=mergeSort(nums, mid+1, right);//统计一左一右逆序对个数int cur1 = left, cur2 = mid +1;int i = left;while(cur1 <= mid){while(cur2 <= right && nums[cur1]/2.0<= nums[cur2]) cur2++;if(cur2 > right)break; ret +=(right - cur2 +1); cur1++;}//治：合并两个有序数组 cur1 = left; cur2 = mid +1;while(cur1 <= mid && cur2 <= right){if(nums[cur1]< nums[cur2]) tmp[i++]= nums[cur2++];else tmp[i++]= nums[cur1++];}while(cur1 <= mid) tmp[i++]= nums[cur1++];while(cur2 <= right) tmp[i++]= nums[cur2++];//还原for(int j = left; j <= right; j++){ nums[j]= tmp[j];}return ret;}}4.2 暴力枚举
解题思路：
- 直接两层for循环即可
- 会超时
解题代码：
//时间复杂度：O(n^2)//空间复杂度：O(1)classSolution{publicintreversePairs(int[] nums){int ret =0;for(int i =0; i < nums.length; i++){for(int j = i+1; j < nums.length; j++){if(nums[i]/2.0> nums[j]) ret++;}}return ret;}}
