Java算法OJ（6）归并分治
目录
1.前言
哈喽大家好吖，今天继续来给大家带来Java算法——归并分治的讲解，学习这篇的前提可以先把我的上一篇的归并排序学习完毕哦。
废话不多说让我们来开始吧。
2.正文
2.1归并分治的概念
我们知道了何为归并排序，归并的本质是将小问题处理完成后合成大问题依次逐步来解决，然后再来排序，那么归并分治呢？其实归并排序就是归并分治的经典案例，只是不局限于排序这个问题还可以拓展到其他问题上，许多类似的问题都可以通过归并分治来解决。
接下来来详细讲解归并分治的思想和根本逻辑：
归并分治是一种重要的算法设计范式，它通过递归地将问题分解为更小的子问题来解决，然后将子问题的解合并以得到原问题的解。归并分治与分治法（Divide and Conquer）密切相关，但更侧重于“归并”步骤，即将分解后的部分合并成最终的解。这种方法在许多算法中都有应用，包括归并排序、快速傅里叶变换等。
归并分治的基本步骤：
- 分解：将原问题分解成若干个较小的、但结构与原问题相似的子问题。
- 解决：递归地解决这些子问题。如果子问题足够小，可以直接解决。
- 合并：将子问题的解合并成原问题的解。
那么总结一下能被归并分治思想处理的问题的共同点：
- 看一下是否在一个范围上这个问题可以等于左部分的答案+右部分的答案+跨越左右的答案。
- 是否左右俩侧在有序之后可以更好的解决这个问题。
至于为什么会有这俩个关键，相信你看完下面俩到例题会理解的。
2.2计算数组的小和
计算数组的小和_牛客题霸_牛客网
https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469
2.2.1题目
2.2.2示例
2.2.3代码
先附上这道题得讲解：
全部都遍历一遍的话显然时间复杂度过不去，那么有些同学可能会有些疑惑，这道题从哪里看体现了归并得思想？又是从哪里需要我们实现排序，下端代码为什么要实现排序的功能，让我们来一一分析。
- 拿题目中的示例一来分析，将其看成俩半135和246，题目中俩半甚至是恰好完成排序后的俩半（示例提醒我们用归并），当然这不是关键，关键的是排序是否可以增加我们解决这道题的便利性。
- 如果俩侧的数组均是有序的，我们就可以通过左右指针分别卡住左右俩侧的首端，来求“左部分的答案+右部分的答案+跨越左右的答案”中最重要的跨越左右的答案。
- 若左指针指向的数字小于右侧，那么左侧指针往右移动，右侧指针不动，ans+=sum。
- 若右指针指向的数字小于左侧，那么右侧指针向右移动，左侧指针不懂，此时再次比较左右指针分别指向的数字大小，按照这俩种情况来处理
- 跨越左右的答案处理完毕，那么纯左侧和纯右侧呢，显然，把它分解成更小的问题时，已经变成更小问题的“跨越左右的答案了”，即已经处理过，且处理过后俩侧变得有序，会更加方便我们进行这个遍历。
TIPS：我们需要注意的是，这个做右指针卡住遍历并不是一件时间复杂度很高的事情，它仅把左右俩侧总共遍历了一遍（可以在稿纸模拟一遍流程），即没有反复遍历使时间复杂度高。
附上代码：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static int MAXN = 100001;
public static int[] arr = new int[MAXN];//用于存储原有数组
public static int[] help = new int [MAXN];//归并排序需要的辅助数组
public static int n;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
for(int i = 0;i < n;i++){
arr[i] = scanner.nextInt();
}
System.out.println(smallSum(0,n - 1));
}
public static long smallSum(int l,int r){
if(l == r)return 0;
int mid = (l + r)/2;
return smallSum(l,mid) + smallSum(mid + 1,r) + mergeSort(l,mid,r);
}
//在完成排序的同时完成计数
public static long mergeSort(int l,int m,int r) {
long ans = 0;
for (int a = l, b = m + 1, sum = 0; b <= r; b++) {
while (a <= m && arr[a] <= arr[b]) {
sum += arr[a++];
}
ans += sum;
}
int x = l;//左指针
int y = m + 1;//右指针
int z = l;
while (x <= m && y <= r) {
help[z++] = arr[x] <= arr[y] ? arr[x++] : arr[y++];
}
while (x <= m) {
help[z++] = arr[x++];
}
while (y <= r) {
help[z++] = arr[y++];
}
for (int i = l; i <= r; i++) {
arr[i] = help[i];
}
return ans;
}
}2.3翻转对
493. 翻转对 - 力扣（LeetCode）https://leetcode.cn/problems/reverse-pairs/description/
2.3.1题目
2.3.2示例
2.3.3代码
这道题思路跟上一道题类似，不多赘述，只是在处理统计的时候条件变化了而已，核心逻辑和归并排序都没变。有疑问欢迎在评论区交流。
class Solution {
public static int MAXN = 50001;
public static int[] help = new int[MAXN];
public static int reversePairs(int[] arr) {
return counts(arr, 0, arr.length - 1);
}
public static int counts(int[] arr, int l, int r) {
if (l == r) {
return 0;
}
int m = (l + r) / 2;
return counts(arr, l, m) + counts(arr, m + 1, r) + merge(arr, l, m, r);
}
public static int merge(int[] arr, int l, int m, int r) {
// 计算处理部分
int ans = 0;
for(int x = l,y = m + 1;x <= m;x++){
while(y <= r && (long)arr[x] > (long) 2 * arr[y] ){
y++;
}
ans += y - m -1;
}
// 归并排序
int i = l;
int a = l;
int b = m + 1;
while (a <= m && b <= r) {
help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
}
while (a <= m) {
help[i++] = arr[a++];
}
while (b <= r) {
help[i++] = arr[b++];
}
for (i = l; i <= r; i++) {
arr[i] = help[i];
}
return ans;
}
}3.小结
今天的分享到这里就结束了，喜欢的小伙伴点点赞点点关注，你的支持就是对我最大的鼓励，大家加油！
原文地址：https://blog.csdn.net/2301_81073317/article/details/143595498
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！