Java算法OJ(6)归并分治


目录

1.前言

2.正文

2.1归并分治的概念

2.2计算数组的小和

2.2.1题目

2.2.2示例

2.2.3代码

2.3翻转对

2.3.1题目

2.3.2示例

2.3.3代码

3.小结


1.前言

哈喽大家好吖,今天继续来给大家带来Java算法——归并分治的讲解,学习这篇的前提可以先把我的上一篇的归并排序学习完毕哦。

传送门:java算法OJ(5)归并排序-CSDN博客文章浏览阅读986次,点赞63次,收藏63次。哈喽大家好吖,今天来给大家分享Java中一个比较高效的算法——归并排序,这个相比于最初学的所谓的“三傻排序”(选择排序、冒泡排序和插入排序)在复杂度上优化了许多,那让我们废话不多说,开始今天的学习吧。https://blog.csdn.net/2301_81073317/article/details/143115610?spm=1001.2014.3001.5501

废话不多说让我们来开始吧。 

2.正文

2.1归并分治的概念

我们知道了何为归并排序,归并的本质是将小问题处理完成后合成大问题依次逐步来解决,然后再来排序,那么归并分治呢?其实归并排序就是归并分治的经典案例,只是不局限于排序这个问题还可以拓展到其他问题上,许多类似的问题都可以通过归并分治来解决。

接下来来详细讲解归并分治的思想和根本逻辑:

归并分治是一种重要的算法设计范式,它通过递归地将问题分解为更小的子问题来解决,然后将子问题的解合并以得到原问题的解。归并分治与分治法(Divide and Conquer)密切相关,但更侧重于“归并”步骤,即将分解后的部分合并成最终的解。这种方法在许多算法中都有应用,包括归并排序、快速傅里叶变换等。

归并分治的基本步骤:

  1. 分解:将原问题分解成若干个较小的、但结构与原问题相似的子问题。
  2. 解决:递归地解决这些子问题。如果子问题足够小,可以直接解决。
  3. 合并:将子问题的解合并成原问题的解。

那么总结一下能被归并分治思想处理的问题的共同点:

  • 看一下是否在一个范围上这个问题可以等于左部分的答案+右部分的答案+跨越左右的答案。
  • 是否左右俩侧在有序之后可以更好的解决这个问题。

至于为什么会有这俩个关键,相信你看完下面俩到例题会理解的。

2.2计算数组的小和

计算数组的小和_牛客题霸_牛客网icon-default.png?t=O83Ahttps://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469

2.2.1题目

2.2.2示例

2.2.3代码

先附上这道题得讲解:

全部都遍历一遍的话显然时间复杂度过不去,那么有些同学可能会有些疑惑,这道题从哪里看体现了归并得思想?又是从哪里需要我们实现排序,下端代码为什么要实现排序的功能,让我们来一一分析。


  • 拿题目中的示例一来分析,将其看成俩半135和246,题目中俩半甚至是恰好完成排序后的俩半(示例提醒我们用归并),当然这不是关键,关键的是排序是否可以增加我们解决这道题的便利性。
  • 如果俩侧的数组均是有序的,我们就可以通过左右指针分别卡住左右俩侧的首端,来求“左部分的答案+右部分的答案+跨越左右的答案”中最重要的跨越左右的答案。
  1. 若左指针指向的数字小于右侧,那么左侧指针往右移动,右侧指针不动,ans+=sum。
  2. 若右指针指向的数字小于左侧,那么右侧指针向右移动,左侧指针不懂,此时再次比较左右指针分别指向的数字大小,按照这俩种情况来处理
  • 跨越左右的答案处理完毕,那么纯左侧和纯右侧呢,显然,把它分解成更小的问题时,已经变成更小问题的“跨越左右的答案了”,即已经处理过,且处理过后俩侧变得有序,会更加方便我们进行这个遍历。

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)icon-default.png?t=O83Ahttps://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.小结

今天的分享到这里就结束了,喜欢的小伙伴点点赞点点关注,你的支持就是对我最大的鼓励,大家加油!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/910652.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【网络】自定义协议——序列化和反序列化

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;了解什么是序列化和分序列&#xff0c;并且自己能手撕网络版的计算器。 > 毒鸡汤&#xff1a;有些事情&#xff0c;总是不明白&#xff0c;所以我不…

Abaqus随机骨料过渡区孔隙三维网格插件:Random Agg ITZ Pore 3D (Mesh)

插件介绍 Random Agg ITZ Pore 3D (Mesh) V1.0 - AbyssFish 插件可在Abaqus内参数化建立包含水泥浆基体、粗细骨料、界面过渡区&#xff08;ITZ&#xff09;、孔隙在内的多相材料混凝土细观背景网格模型。 模型说明 插件采用材料映射单元的方式&#xff0c;将不同相材料赋值…

【含开题报告+文档+源码】基于SpringBoot+Vue智能居民健康检测系统设计与实现

开题报告 随着社会发展和人民生活水平的提高&#xff0c;人们对健康生活的要求越来越高。而广大居民由于条件限制&#xff0c;存在着健康管理服务不足的问题。本文基于JavaWeb技术&#xff0c;设计并实现了一种居民健康检测系统。首先&#xff0c;本文对该平台的需求进行了分析…

基于Multisim8路抢答器电路仿真电路(含仿真和报告)

【全套资料.zip】8路抢答器电路仿真电路Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 1.设计数字式抢答器&#xff0c;每组选手具有一个抢答按钮。 2.电路具有第一抢答信号的鉴别和锁存…

Java 网络编程(一)—— UDP数据报套接字编程

概念 在网络编程中主要的对象有两个&#xff1a;客户端和服务器。客户端是提供请求的&#xff0c;归用户使用&#xff0c;发送的请求会被服务器接收&#xff0c;服务器根据请求做出响应&#xff0c;然后再将响应的数据包返回给客户端。 作为程序员&#xff0c;我们主要关心应…

人工智能学习--归一化(Normalization)

概念 归一化是数据预处理中将不同量纲的特征数据缩放至同一尺度的过程&#xff0c;使特征值落在同一范围&#xff08;如[0, 1]或[-1, 1]&#xff09;。归一化有助于消除量纲影响&#xff0c;提升算法的收敛速度和模型稳定性&#xff0c;尤其在梯度下降和距离计算等算法中尤为重…

高校实验室安全巡检系统设计与实现(源码+定制+开发)高校实验室巡检系统、实验室安全管理平台、实验室安全监控系统、智能实验室巡查系统、高校实验室风险管理

博主介绍&#xff1a; ✌我是阿龙&#xff0c;一名专注于Java技术领域的程序员&#xff0c;全网拥有10W粉丝。作为CSDN特邀作者、博客专家、新星计划导师&#xff0c;我在计算机毕业设计开发方面积累了丰富的经验。同时&#xff0c;我也是掘金、华为云、阿里云、InfoQ等平台…

解决程序因缺少xinput1_3.dll无法运行的有效方法,有效修复丢失xinput1_3.dll

如果你的电脑在运行某些应用程序或游戏时提示“xinput1_3.dll丢失”或“找不到xinput1_3.dll”的错误消息&#xff0c;那么很可能是因为你的系统中缺少这个重要的DLL文件而导致的问题。那么电脑出现xinput1_3.dll丢失的问题时有哪些方法进行修复呢&#xff1f; 如何确定电脑是否…

论文笔记(五十四)pi0: A Vision-Language-Action Flow Model for General Robot Control

π0: A Vision-Language-Action Flow Model for General Robot Control 文章概括摘要I. INTRODUCTIONII. RELATED WORKIII. OVERVIEWIV. π 0 \pi_0 π0​模型V. 数据收集和培训配方A. 预训练和后训练B. 语言和高级策略C. 机器人系统细节 VI. 实验评估A. 基础模型评估B. 遵循语…

Redis 基础数据改造

优质博文&#xff1a;IT-BLOG-CN 一、服务背景 基础数据查询服务&#xff1a;提供航司&#xff08;5000家&#xff09;、机场&#xff08;4000&#xff09;、票台&#xff08;40000&#xff09;、城市&#xff08;4000&#xff09;等基础数据信息。 痛点一&#xff1a;因为基…

C# String系列(3):StringBuilder有诸多优势,它能代替String吗?

前言 嗨&#xff0c;大家好&#xff01; 之前我们在文章《C# String 类型&#xff1a;那些你可能不知道的秘密》分享了 C# String 类型的一些小秘密和小技巧&#xff0c;其中提到一个性能提升的小贴士&#xff1a;在拼接字符串时&#xff0c;使用 StringBuilder 替代 String。…

6.1、实验一:静态路由

源文件获取&#xff1a;6.1_实验一&#xff1a;静态路由.pkt: https://url02.ctfile.com/f/61945102-1420248902-c5a99e?p2707 (访问密码: 2707) 一、目的 理解路由表的概念 会使用基础命令 根据需求正确配置静态路由 二、准备实验 1.实验要求 让PC0、PC1、PC2三台电脑…

嵌入式linux中设备树控制硬件的方法

大家好,今天主要给大家分享一下,如何使用linux系统下的设备树进行硬件控制方法。 第一:linux系统中设备树驱动LED原理 在linux系统中可以使用设备树向Linux内核传递相关的寄存器地址,linux驱动中使用OF函数从设备树中获取所需的属性值,然后使用获取到的属性值来初始化相关…

一文解秘Rust如何与Java互操作

本博客所有文章除特别声明外&#xff0c;均采用CC BY-NC-SA 4.0许可协议。转载请注明来自 唯你 使用场景 JAVA 与 Rust 互操作让 Rust 可以背靠 Java 大生态来做更多事情&#xff0c;而 Java 也可以享受 Rust 语言特性的内存安全&#xff0c;所有权机制&#xff0c;无畏并发。…

【贪心算法】No.1---贪心算法(1)

文章目录 前言一、贪心算法&#xff1a;二、贪心算法示例&#xff1a;1.1 柠檬⽔找零1.2 将数组和减半的最少操作次数1.3 最⼤数1.4 摆动序列1.5 最⻓递增⼦序列1.6 递增的三元⼦序列 前言 &#x1f467;个人主页&#xff1a;小沈YO. &#x1f61a;小编介绍&#xff1a;欢迎来到…

阿里云-防火墙设置不当导致ssh无法连接

今天学网络编程的时候&#xff0c;看见有陌生ip连接&#xff0c;所以打开了防火墙禁止除本机之外的其他ip连接&#xff1a; 但是当我再次用ssh的时候&#xff0c;连不上了才发现大事不妙。 折腾了半天&#xff0c;发现阿里云上可以在线向服务器发送命令&#xff0c;所以赶紧把2…

基于物联网设计的地下煤矿安全监测与预警

文章目录 一、前言1.1 项目介绍【1】项目开发背景【2】设计实现的功能【3】项目硬件模块组成 1.2 设计思路1.3 系统功能总结1.4 开发工具的选择【1】设备端开发【2】上位机开发 1.5 模块的技术详情介绍【1】NBIOT-BC26模块【2】MQ5传感器【4】DHT11传感器【5】红外热释电人体检…

揭秘全向轮运动学:机动艺术与上下位机通信的智慧桥梁

✨✨ Rqtz 个人主页 : 点击✨✨ &#x1f308;Qt系列专栏:点击 &#x1f388;Qt智能车上位机专栏: 点击&#x1f388; 本篇文章介绍的是有关于全向轮运动学分析&#xff0c;单片机与上位机通信C代码以及ROS里程计解算的内容。 目录 大纲 ROS&#xff08;机器人操作系统&…

《AI在企业战略中的关键地位:以微软和阿里为例》

内容概要 在当今商业环境中&#xff0c;人工智能&#xff08;AI&#xff09;的影响力如滔滔洪水&#xff0c;愈演愈烈。文章将揭示AI在企业战略中的崛起&#xff0c;尤其以微软和阿里巴巴为代表的企业&#xff0c;这两家科技巨头通过不同方式&#xff0c;将智能技术融入其核心…

Pandas | 理性判断数据是否存在缺失值的一种方法

理性判断 一般思路进一步思考df[B].explode() 一般思路 tcc.info()上述信息info显示没有缺失值 但是真实的情况还是要根据业务实际分析tcc.isnull().sum() # 和tcc.info()作用和tcc.info() 其实是一样的 进一步思考 在此过程中&#xff0c;我们需要检验是否存在采用别的值来表…