【Java 优选算法】分治-归并排序

欢迎关注个人主页：逸狼

---

创造不易，可以点点赞吗~

如有错误，欢迎指出~

---

---

数组分块如二叉树的前序遍历, 而归并排序就如二叉树的后序遍历 

912. 排序数组

解法

使用归并算法

1. 根据中间点划分区间, mid =(right + left ) / 2
2. 将左右区间排序
3. 合并两个有序数组
4. 处理没有遍历完的数组
5. 将排好序的数组tmp覆盖到原数组nums里

优化: 将tmp数组new成一个全局变量,减少频繁的空间开销

代码

class Solution {int[] tmp;public int[] sortArray(int[] nums) {int n = nums.length;tmp = new int[n];mergeSort(nums, 0, n - 1);return nums;}public void mergeSort(int[] nums, int left, int right){if(left >= right) return;//1.找到中间点midint mid = (left + right) / 2;//2.左右排好序mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);//3.合并有序数组 [left, mid] [mid + 1, right]int cur1 = left, cur2 = mid + 1, i = 0;while(cur1 <= mid && cur2 <= right){tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++];}//处理没有遍历完的数组while(cur1 <= mid) tmp[i++] = nums[cur1++];while(cur2 <= right) tmp[i++] = nums[cur2++];//4.tmp覆盖numsfor(int j = left; j <= right; j++){nums[j] = tmp[j - left];}}
}

LCR 170. 交易逆序对的总数（数组中的逆序对）

解法

解法一: 暴力枚举: 两层for循环

解法二: 分治,N*logN

将数组通过mid分为两部分,

1. 先找左半部分的逆序对, 再左排序
2. 再找右半部分的逆序对, 再右排序
3. 最后找一左一右组合的逆序对(此时左数组和右数组分别都是有序的),再合并排序

策略一: 找出该数(nums[cur1] )之前,有多少个(mid - cur2 + 1)数比我(nums[cur2] )大.

• 当nums[cur1] <= nums[cur2] 时 , cur1++;
• 当nums[cur1] > nums[cur2]时 ,ret += mid - cur1 + 1, cur2++

策略二: 找出该数(nums[cur1] )之后,有多少个(right - cur2 + 1)数比我(nums[cur2] )小.

• 当nums[cur1] <= nums[cur2] 时 , cur2++;
• 当nums[cur1] > nums[cur2]时 ,ret += right - cur2 + 1, cur1++

• 时间复杂度：O(nlogn)，这是归并排序的时间复杂度，其中 n 是数组的长度。
• 空间复杂度：O(n)，主要是临时数组 tmp 的空间开销。

代码

class Solution {int[] tmp;public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}public int merge(int[] nums, int left, int right){if(left >= right) return 0;//找出中间点midint mid = (left + right) / 2;int ret = 0;//左右排好序,返回结果ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);//合并有序数组,计算一左一右逆序对int cur1 = left, cur2 = mid + 1, i = 0;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 - left];}return ret;}
}

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

解法

解法: 归并排序

和上一题类似,但是这里只能通过策略二: 降序解决

注意: 最终结果是加在原始数组的下标中 

代码

class Solution {int[] ret;int[] index; //标记 nums中当前元素的原始下标int[] tmpIndex;int[] tmpNums;public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpIndex = new int[n];tmpNums = new int[n];//初始化index数组for(int i = 0; i < n; i++){index[i] = i;}merge(nums, 0, n - 1);List<Integer> l = new ArrayList<>();for(int x : ret){l.add(x);}return l;}public void merge(int[] nums, int left, int right){if(left >= right) return;int mid = (left + right) / 2;merge(nums, left, mid);merge(nums, mid + 1, right);//[left, mid] [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(int j = left; j <= right; j++){nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
}

493. 翻转对

解法

注意: 要先统计结果后,再进行排序

边界情况, 可以将2倍的数转为long,也可以使用 / 2.0 

代码

 策略一: 降序,谁大谁在前面

class Solution {int[] tmp; public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}public int merge(int[] nums, int left, int right){if(left >= right) return 0;int mid = (left + right) / 2, ret = 0;ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);//[left, mid] [mid + 1, right]//先统计,后归并int x = left, y = mid + 1;while(x <= mid && y <= right){//降序if(nums[x] / 2.0 > nums[y] ){ret += right - y + 1;x++;}else{                y++;}}int cur1 = left, cur2 = mid + 1, i = 0;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 - left];}return ret;}
}

策略二: 升序

class Solution {int[] tmp; public int reversePairs(int[] nums) {int n = nums.length;tmp = new int[n];return merge(nums, 0, n - 1);}public int merge(int[] nums, int left, int right){if(left >= right) return 0;int mid = (left + right) / 2, ret = 0;ret += merge(nums, left, mid);ret += merge(nums, mid + 1, right);//[left, mid] [mid + 1, right]//先统计,后归并int x = left, y = mid + 1;while(x <= mid && y <= right){//降序if(nums[x] / 2.0 > nums[y] ){ret += mid - x + 1;y++;}else{                x++;}}int cur1 = left, cur2 = mid + 1, i = 0;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 - left];}return ret;}
}