当前位置: 首页 > news >正文

10.23归并排序

课上

归并排序 

最大时,就是两个都是完全倒序,但注意一定有一个序列先用完,此时剩一个序列只有一个元素,不用比较,直接加入,所以就是n+n-1,

最小时,是都是完全有序,且一个序列中的元素完全,全部小于另一个序列中元素,但每次都需要第一个值进行比较,直到小的序列全用完,就直接一直不用比较加剩下的序列中元素

自顶向下

 自底向上

这个意思是说,确定外层确定子序列的长度,然后每次都从这个序列的头部开始,逐渐合并外层确定长度的子序列,即内层循环为不断归并两个长度相同(为外层确定的长度)的子序列,直到左子序列的左端到达当前序列的尾部

这句需注意

确定左子序列左端,然后根据当前子序列长度,确定右子序列左端,左子序列右端,由于内层判断是lx<=r-len,所以左子序列右端,右子序列左端一定可以直接加减得到,但是右子序列右端不能确定,所以需要一个min函数

链表合并

经典面试题

极端情况是一直动二号顺序表的元素,那就说明二号顺序表元素都比一号顺序小,那么k到i时,一号顺序表都在对应正确的位置

其他情况下,移动一号顺序表,就意味着一号顺序表长度变短了

另一种极端情况是一直移动一号顺序表,那么k到j时,二号顺序表都在正确位置

如果不倒置,就是在原基础上按大的排,即之前倒置是比较两个表头哪个小,把小的放前面,现在是比较表尾哪个大,把大的放后面,就可以直接在原来基础上排序

逆序对

就是后面的序列表头元素放到前面时,就相当于此时这个元素比前面的所有元素都小,都能构成逆序对,即逆序对数量+前面序列剩余的长度

如果前面的表头元素移动,和后面的不构成逆序对,其内部也在底层递归时统计过,所以就没有逆序对产生,即只在后面序列前移时产生逆序对

翻转对(力扣493)

逆序对依然产生在后面序列中,只不过需要再加一个条件判断 

回顾

 冒泡排序

每次都可以选出一个当前最大值,那么后续比较的时候尾部长度逐渐减小,

每次比较都要从第一个元素开始

void bubbleSort(vector<int>& v){//冒泡排序for(int i = 0; i < v.size(); i++){for(int j = 0; j < v.size() - i - 1; j++){if(v[j] > v[j + 1])swap(v[j], v[j + 1]);}}
}

说让排序完成时

快速排序最快nlogn,最差n^2 

相关文章:

10.23归并排序

课上 归并排序 最大时&#xff0c;就是两个都是完全倒序&#xff0c;但注意一定有一个序列先用完&#xff0c;此时剩一个序列只有一个元素&#xff0c;不用比较&#xff0c;直接加入&#xff0c;所以就是nn-1, 最小时&#xff0c;是都是完全有序&#xff0c;且一个序列中的元…...

[C++]:2初识C++(auto) + 类和对象上:

[TOC](初识C(auto) 类和对象上) 一.初始C 1.auto关键字&#xff1a;(C11) 1.作为一个变量的类型给这个类型初始化&#xff0c;auto自动识别初始化这个变量值的类型&#xff0c;为auto类型的这个变量开辟一个合适的空间。 补充&#xff1a; 1.typeid(变量名).name—>可以打…...

大学英语试卷

大学英语试卷 If everyone learns to set forth facts and reason things out in social life, many of the contradictions are easy to ____. A. oblige B. engage C. resolve D. commitIf we let the fastest runner set the____, the others will fall behind. A. pace B.…...

SpringBoot Lombok的使用

目录 下载Lombok插件 Lombok的用法 获取日志对象 生成get,set方法 Lombok框架的实现原理 Lombok的常用注解 下载Lombok插件 要使用Lombok首先要确保idea安装了lombok插件 在项目中添加 lombok依赖 在<dependency>里右键生成点击edit starters 插件(没有就下载,可…...

后台管理系统SQL注入漏洞

对于edu来说&#xff0c;是新人挖洞较好的平台&#xff0c;本次记录一次走运的捡漏0x01 前景 在进行fofa盲打站点的时候&#xff0c;来到了一个后台管理处看到集市二字&#xff0c;应该是edu站点 确认目标身份&#xff08;使用的quake进行然后去ipc备案查询&#xff09; 网…...

变量常用函数

查看变量类型 type(变量名) 用来查询变量所指的对象类型 >>> a, b, c, d 20, 5.5, True, 43j >>> print(type(a), type(b), type(c), type(d)) <class int> <class float> <class bool> <class complex> 基础数据类型 # coding…...

从零学算法(LCR 157)

某店铺将用于组成套餐的商品记作字符串 goods&#xff0c;其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。 返回结果 无顺序要求&#xff0c;但不能含有重复的元素。 示例 1: 输入&#xff1a;goods “agew” 输出&#xff1a;[“aegw”,“aewg”,“ag…...

mysql 优化 聚簇索引=主键索引吗

在 InnoDB 引擎中&#xff0c;每张表都会有一个特殊的索引“聚簇索引”&#xff0c;也被称之为聚集索引&#xff0c;它是用来存储行数据的。一般情况下&#xff0c;聚簇索引等同于主键索引&#xff0c;但这里有一个前提条件&#xff0c;那就是这张表需要有主键&#xff0c;只有…...

c# ManualResetEvent WaitHandle 实现同步

//本文演示了ManualResetEvent 类的非静态set()、Reset()、WaitOne()和 //WaitHandle类的静态方法WaitAllWaitAll() //它们用于线程间的同步控制。 //实现了如下功能&#xff1a;线程1&#xff08;定时控制&#xff09;通知线程2和线程3采集数据 //线程2和3数据采集完了&am…...

使用Packstack安装器安装一体化OpenStack云平台

【实训目的】 初步掌握OpenStack快捷安装的方法。掌握OpenStack图形界面的基本操作。 【实训准备】 &#xff08;1&#xff09;准备一台能够安装OpenStack的实验用计算机&#xff0c;建议使用VMware虚拟机。 &#xff08;2&#xff09;该计算机应安装CentOS 7&#xff0c;建…...

【Rust】4 一文讲解重点 pattern matching | trait | 生命周期 | 闭包 | 迭代器 | 智能指针 | 并发与并行

文章目录 一、pattern matching二、trait2.1 常见 trait2.1.1 Copy 和 Clone2.1.2 PartialEq 和 Eq2.1.3 PartialOrd 和 Ord2.1.4 Hash2.1.5 From, Into, TryFrom, TryInto 2.2 概念2.2.1 关联类型2.2.2 关联常量2.3.3 泛型关联类型2.3.3.1 示例: 用泛型关联类型, 创建集合工厂…...

idea Java代码格式化规范

文章目录 引入基础知识代码模板idea模板eclipse模板1.安装插件2.生成配置文件3.导入配置文件 附录一&#xff1a;xml配置项说明附录二&#xff1a;赠送 引入 最近在公司开发中&#xff0c;遇到了一点小问题&#xff0c;组内各同事的格式化规范不一致。一来导致代码样式并不统一…...

apple MFI工厂认证,干货,为防止MFI工作人员查看,已设置VIP阅读

一开始以为审核特别严格,准备了好久,经历过了之后会发现很简单,1个小时完成了所有审核事项。 好好招待审计员,比如能接送就接送,到点吃饭就尽量约时间吃饭后再审计,找个正式的会议室,该摆盘水果就摆上,让审计员感觉到公司是很重视这次的MFI审核,但是不能贿赂发红包那…...

软件企业知识库应用场景?如何搭建软件企业知识库?

想要减少人工干预、减少不必要的时间和人力成本、快速获取准确信息……这些应用场景对于我们企业来说是非常渴望在短期内实现的。 软件企业知识库 因为传统知识库仅仅是存储&#xff1a;知识只是“存储”&#xff0c;根本用不起来&#xff0c;缺乏有效的管理方式和储存载体&am…...

华为OD 滑动窗口最大值(100分)【java】B卷

华为OD统一考试A卷+B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目,A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载,请点击以下链接进入: 我用夸克网盘分享了「华为O…...

软件测试 (用例篇)

前言 上一篇博客讲述的是一次基本的测试过程。 在我们开始做了一段时间基础测试&#xff0c;熟悉了业务之后&#xff0c;往往会分配来写测试用例&#xff0c;并且在日常测试中&#xff0c;有时也需要补充测试用例到现有的案例库中。 在这里我们将回答以下问题 1、测试用例的…...

5G技术的飞速发展:连接未来

随着科技的日益进步&#xff0c;5G通讯技术已经成为了全球科技领域的热门话题。5G&#xff0c;即第五代移动通信技术&#xff0c;带来的不仅仅是更快的网络速度&#xff0c;它的高带宽和低延迟特性将为未来的数字世界奠定基础。 速度与效率的飞跃: 5G技术的最大亮点是它极高的下…...

linux进程管理,一个进程的一生(喂饭级教学)

这篇文章谈谈linux中的进程管理。 一周爆肝&#xff0c;创作不易&#xff0c;望支持&#xff01; 希望对大家有所帮助&#xff01;记得收藏&#xff01; 要理解进程管理&#xff0c;重要的是周边问题&#xff0c;一定要知其然&#xff0c;知其所以然。看下方目录就知道都是干货…...

【SA8295P 源码分析 (四)】51 - QNX NFS Server + Android NFS Client 完整配置

【SA8295P 源码分析】51 - QNX NFS Server + Android NFS Client 完整配置 一、QNX 侧 NFS Server 修改:ip 为 192.168.118.21.1 配置拷贝 nfsd、rpcbind 到 /mnt 目录下1.2 配置 exports1.3 为NFS 共享目录挂载镜像1.4 修 startup.sh 开机自启动 nfsd Server1.5 关闭 QNX 防火…...

2023年10月23日--10月29日(主攻光追视频教程)

最好每周完成一样&#xff0c;将来每月完成一样&#xff0c;有成就感。也免得周末迷茫。 光锥目前还有56节&#xff0c; 周二到周五每天4小节。周六日每天20小节&#xff0c;应该可以完成。 即&#xff1a; 周二&#xff1a;9.5-9.8 周三&#xff1a;9.9-10.3 周四&#xff1a…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

九天毕昇深度学习平台 | 如何安装库?

pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子&#xff1a; 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...