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

数据结构面试常见问题之Insert or Merge

😀前言
本文将讨论如何区分插入排序和归并排序两种排序算法。我们将通过判断序列的有序性来确定使用哪种算法进行排序。具体而言,我们将介绍判断插入排序和归并排序的方法,并讨论最小和最大的能区分两种算法的序列长度。

🏠个人主页:尘觉主页

💕欢迎大家:这里是CSDN,我总结知识的地方,欢迎来到我的博客,感谢大家的观看🥰
如果文章有什么需要改进的地方还请大佬不吝赐教 先在次感谢啦😊

文章目录

  • Insert or Merge
    • 习题-IOM.1 插入排序的判断
      • 题意理解
      • 捏软柿子算法
    • 习题-IOM.2 归并段的判断
      • 判断归并段的长度
    • 其他数据测试
    • 😄总结

Insert or Merge

习题-IOM.1 插入排序的判断

题意理解

如何区分简单插入和非递归的归并排序

  1. 插入排序:前面有序,后面没有变化
  2. 归并排序:分段有序
    在这里插入图片描述

捏软柿子算法

ps:在插入和归并两种算法里,哪种算法比较容易判断?插入排序
判断是否插入排序

  1. 从左向右扫描,直到发现顺序不对,跳出循环

  2. 从跳出地点继续向右扫描,与原始序列比对,发现不同则判断为"非"(如果是插入排序的话,所有的元素都是跟原始序列一模一样的)
    如果在对比的过程中发现不同,则跳出循环

  3. 循环自然结束,则判断为"是",返回跳出地点

    1. 解析:(我们可以返回一个布尔值,例如非为0、是为1,但如果我返回的是"是"的话,插入排序要往下进行一步,简单返回一个1在我进行插入排序下一步的时候,还得从左向右扫描去找那个要执行下一步的那个点。所以我们返回"是"的)同时返回一个跳出的地点

如果是插入排序,则从跳出地点开始进行一趟插入

习题-IOM.2 归并段的判断

判断归并段的长度

错误的想法:

  1. 从头开始连续有序的子列长度?
    在这里插入图片描述
  2. 所有连续有序子列的最短长度?
    在这里插入图片描述
    1. 这个其实是四个一段的,但前8个刚好都是有序的
    2. 保险正确的判断方法:从原始序列出发,真的在做归并排序,每归并一趟就把归并的中间结果跟这个结果的序列做一个比对。什么时候每一个数都对上了就再把当前的归并多执行一次然后
      输出结果
3.for (l=2;l<=N;l*=2)
//在保证了l是4的情况下,要检查看能不能是8,
//我们要重复前面的步骤看两段之间的衔接点是不是有序

在这里插入图片描述
红色位置没有序了跳出循环(此时l为4,我们直接以4为归并段继续执行下一趟的归并就可以了)
在这里插入图片描述

其他数据测试

最小N(应该是多大?)
ps:边界测试是每道题里面测试非常重要的一个组成部分
N会是1吗?N等于1会出现什么情形?

N等于1就意味着整个序列里面只有一个数字,在排序前它是一个数字,在排序之后他仍然是同一
个数字,在这种情况下我不管是使用插入排序还是归并排序得到的都会是同样的结果,这样解就不
是唯一的。我们题目输出的要求是插入排序或者归并排序的其中一个,所以N=1是绝对不可以的

保证可以区分两种算法的最小N应该是:4(区分插入排序与归并排序最小要求)

  1. 插入排序第一步,什么都没变
  2. 归并排序第一步,什么都变了

尾部子列无变化,但前面变了(归并)最大N

😄总结

通过本文的介绍,我们了解了如何判断插入排序和归并排序两种算法。对于插入排序,我们可以通过从左到右扫描序列并与原始序列进行比对,如果遇到不同的元素,则判断为归并排序;如果扫描结束后没有发现不同的元素,则判断为插入排序。而对于归并排序,我们可以通过多次归并并将归并的中间结果与原始序列进行比对,直到每个元素都匹配成功,即可判断为归并排序。

此外,我们还讨论了最小和最大能区分插入排序和归并排序的序列长度。最小长度为4,因为在长度为4的序列中,插入排序的第一步不会改变序列的顺序,而归并排序的第一步会改变序列的顺序。而最大长度没有明确的界限,因为归并排序可以应对任意长度的序列。

通过掌握这些判断方法和序列长度的特点面试就不用担心啦祝您成功

😁热门专栏推荐
想学习vue的可以看看这个

java基础合集

数据库合集

redis合集

nginx合集

linux合集

手写机制

微服务组件

spring_尘觉

springMVC

mybits

等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持

🤔欢迎大家加入我的社区 尘觉社区

文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

相关文章:

数据结构面试常见问题之Insert or Merge

&#x1f600;前言 本文将讨论如何区分插入排序和归并排序两种排序算法。我们将通过判断序列的有序性来确定使用哪种算法进行排序。具体而言&#xff0c;我们将介绍判断插入排序和归并排序的方法&#xff0c;并讨论最小和最大的能区分两种算法的序列长度。 &#x1f3e0;个人主…...

perl 用 XML::LibXML 解析 Freeplane.mm文件,XML文件

Perl 官网 www.cpan.org 从 https://strawberryperl.com/ 下载网速太慢了 建议从 https://download.csdn.net/download/qq_36286161/87892419 下载 strawberry-perl-5.32.1.1-64bit.zip 约105MB 解压后安装.msi&#xff0c;装完后有520MB&#xff0c;建议安装在D:盘 在云计算…...

Spring Cloud Alibaba微服务从入门到进阶(七)(服务容错-Sentinel)

雪崩效应 我们把基础服务故障&#xff0c;导致上层服务故障&#xff0c;并且这个故障不断放大的过程&#xff0c;成为雪崩效应。 雪崩效应&#xff0c;往往是因为服务没有做好容错造成的。 微服务常见容错方案 仓壁模式 比如让controller有自己独立的线程池&#xff0c;线程池满…...

Arduino RP2040 + SSD1306 I2C OLED +LittleFS存储GBK字库实现中文显示

Arduino RP2040 + SSD1306 I2C OLED +LittleFS存储GBK字库实现中文显示 📌LittleFS插件安装,可以参考《Arduino RP2040 LittleFS的使用介绍》🎈相关内容《Arduino esp8266 软件I2C SSD1306 +LittleFS存储GBK字库实现中文显示》🔖基于Earle F. Philhower, III的核心固件开…...

代码随想录算法训练营第day53|1143.最长公共子序列 、 1035.不相交的线、 53. 最大子序和 动态规划

目录 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 1143.最长公共子序列 力扣题目链接(opens new window) 给定两个字符串 text1 和 text2&#xff0c;返回这两个字符串的最长公共子序列的长度。 一个字符串的 子序列 是指这样一个新的字符串&#xff1a;它是由原…...

【Flutter学习笔记】10.2 组合现有组件

参考资料&#xff1a; 《Flutter实战第二版》 10.2 组合现有组件 在Flutter中页面UI通常都是由一些低级别组件组合而成&#xff0c;当我们需要封装一些通用组件时&#xff0c;应该首先考虑是否可以通过组合其他组件来实现&#xff0c;如果可以&#xff0c;则应优先使用组合&…...

C++的vector类(一):vector类的常见操作

目录 前言 Vector类 遍历与初始化vector ​vector的扩容机制 vector的对象操作 find与insert 对象数组 前言 string类中还有一些内容需要注意&#xff1a; STL 的string类怎么啦&#xff1f; C面试中string类的一种正确写法 C STL string的Copy-On-Write技术 C的st…...

SpringBoot注解

Spring Boot 中常用的一些注解及其作用如下所示&#xff1a; SpringBootApplication&#xff1a;标注一个主程序类&#xff0c;用于启动 Spring Boot 应用&#xff0c;通常放在包的最顶层。 RestController&#xff1a;结合 Controller 和 ResponseBody&#xff0c;用于定义 R…...

每日三个JAVA经典面试题(十九)

1.Java Concurrency API 中的 Lock 接口(Lock interface)是什么&#xff1f;对比同步它有什么优势&#xff1f;Java并发API中的Lock接口提供了一种比传统synchronized块或方法更灵活、更强大的线程同步机制。Lock接口允许更细粒度的锁控制&#xff0c;通过它可以实现更复杂的线…...

springboot企业级抽奖项目业务一(登录模块)

开发流程 该业务基于rouyi生成好了mapper和service的代码&#xff0c;现在需要在controller层写接口 实际操作流程&#xff1a; 看接口文档一>controller里定义函数一>看给出的工具类一>补全controller里的函数一>运行测试 接口文档 在登录模块有登录和登出方…...

【Python + Django】启动简单的文本页面

前言&#xff1a; 为了应付&#xff08;bushi&#xff09;毕业论文&#xff0c;总要自己亲手搞一个像模像样的项目出来吧 ~ ~ 希望自己能在新的连载中学到项目搭建的知识&#xff0c;这也算是为自己的测试经历增添光彩吧&#xff01;&#xff01;&#xff01; 希望、希望大家…...

Docker——问题解决:服务器端和Windows端IP互通

踩了大坑&#xff0c;特此记录&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 我在服务器端部署了服务&#xff0c;但是在本地端Windows机器上无法访问&#xff0c;因此卡了一天。 1. 双向Ping通 防火墙导致只能单向Ping通 首先需要解决双向ping通的问题&…...

HTTP跨域

1. 简介 HTTP跨域是指不同域名下的网页请求资源时&#xff0c;由于浏览器同源策略限制&#xff0c;导致请求被阻止。为解决这一问题&#xff0c;开发者常采用跨域资源共享&#xff08;CORS&#xff09;等技术来允许合法跨域请求&#xff0c;确保网站功能正常运行。 同源 协议…...

用Python的turtle库绘制皮卡丘

turtle库的简介 turtle(海龟)库是turtle绘图体系的python实现&#xff0c;turtle库是一种标准库&#xff0c;是python自带的。 turtle(海龟)是一种真实的存在&#xff0c;有一个海龟在窗口的正中心&#xff0c;在画布上游走&#xff0c;走过的轨迹形成了绘制的图形&#xff0…...

C语言打印当前时间

#include <time.h> void print_current_time(char* func_name) { // 获取当前的时间 time_t current_time; time(&current_time); // 将时间转换为本地时间格式 struct tm *local_time localtime(&current_time); // 打印当前的时间 …...

(一)基于IDEA的JAVA基础4

注释文本&#xff0c;注释模版 单行注释://开头放在代码前面&#xff0c;对少部分。 多行注释:快捷方式ctrlshift/,对段落代码注 释。 文档注释:/**……**/&#xff0c;用于声明作者或创作时 间。 文档注释如何设置&#xff0c;首先找到File中…...

【Python】复习12:标准库与第三方库

目录 概念标准库第三方库总结Python 标准库`os` 模块`sys` 模块`json` 模块`re` 模块`datetime` 模块代码示例`os` 模块例子`sys` 模块例子`json` 模块例子`re` 模块例子`datetime` 模块例子第三方库`numpy``pandas``requests`安装第三方库使用第三方库其他一些流行的Python库数…...

CUDA 12介绍

CUDA&#xff08;Compute Unified Device Architecture&#xff09;是由 NVIDIA 开发的并行计算平台和应用程序编程接口&#xff08;API&#xff09;。CUDA 使开发人员能够使用 NVIDIA GPU 进行通用目的的并行计算。CUDA 通过利用 GPU 的大规模并行计算能力来加速各种类型的计算…...

旅游系统-软件与环境

运行 1.下载软件并进行环境配置 2.导入项目包以及SQL文件 (1)VsCode 管理员运行打开 a.新建terminal 注意&#xff1a; 1.执行 npm config set registry https://registry.npm.taobao.org 2.执行 npm install 3.执行 $env:NODE_OPTIONS“–openssl-legacy-provider” b.输入…...

AI基础知识(2)--决策树,神经网络

1.什么是决策树&#xff1f; 决策树是一类常见的机器学习方法&#xff0c;决策树是基于树的结构来进行决策。决策过程中提出的每一个问题都是对于属性的“测试”&#xff0c;决策的最终结论对应了我们希望的判定结果。一个决策树包含一个根节点&#xff0c;若干个内部节点和若…...

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放

简介 前面两期文章我们介绍了I2S的读取和写入&#xff0c;一个是通过INMP441麦克风模块采集音频&#xff0c;一个是通过PCM5102A模块播放音频&#xff0c;那如果我们将两者结合起来&#xff0c;将麦克风采集到的音频通过PCM5102A播放&#xff0c;是不是就可以做一个扩音器了呢…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积

1.题目介绍 给定一个整数数组 nums&#xff0c;返回 数组 answer &#xff0c;其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法&#xff0c;且在 O…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...