【算法】【算法杂谈】两个排序数组中找第k小的数
目录
- 前言
- 问题介绍
- 解决方案
- 代码编写
- java语言版本
- c语言版本
- c++语言版本
- 思考感悟
- 写在最后
前言
当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~
在此感谢左大神让我对算法有了新的感悟认识!
问题介绍
原问题
给定两个数组arr1,arr2,求arr1和arr2合并到一起后,第k小的数是什么
如:
arr1 = [1,2,3]
arr2 = [3,4,5,6]
求第3小的数
结果为3
解决方案
原问题:
参考相同长度的排序数组求上中位数的解法:
https://editor.csdn.net/md?not_checkout=1&articleId=131177400
接下来介绍如何将两个长度不相同的排序数组能够套用上面的办法
首先假设短数组长度10 [0…9]
长数组长度27 [0…26]
总长度为37
- 如果第k小的数中k<shor.len ,也就是k <=10,那么长数组中角标大于k的部分是不会存在第k小的数的,因为后面的数至少都大于k个数,所以问题就变成了 arr1[0…k-1] 和arr2[0…k-1]之间求第k小的数问题了,套用参考即可
- 如果第k小的数范围在 37 - 10 <= k < 37 之间时, 我们知道k后面最多只能有9个数,所以短数组都能选择,长数组可以选的范围只能是27-10到27的范围之间,问题又变成了相同长度数组求上中位数的问题,套用参考即可
- 最后k如果都不满足上面的条件,也就是 10<k<37-10,该怎么办呢?我们假设k = 16,16前面必须有15个数,后面必须有20个数,那么现在我们看下如何补齐。前面15个数,短数组如果全补上去,还剩5个数需要长数组填,那么长数组从第5个位置开始比较,查看是否真的短数组需要补上去(短数组的最大值 < 长数组的第5个位置),如果不小于则从第6个位置开始计算
后面20个如果将短数组全补上去还剩10个需要补,所以长数组中最多能到低16个开始往回走,我们发现长度刚好是10!直接套用公式即可。
代码编写
java语言版本
原问题:
原问题:
/*** 二轮测试:两个排序数组中找到第k小的数* @return*/public static int findKMinFromSortArrCp1(int[] arr1, int[] arr2, int k) {if (k < 1|| arr1 == null || arr2 == null || arr1.length == 0 || arr2.length == 0|| (arr1.length + arr2.length < k)) {throw new RuntimeException("非法入参");}int[][] compareRes = compareArr(arr1, arr2);int[] shortArr = compareRes[0];int[] longArr = compareRes[1];if (k < shortArr.length) {return getUpMidFromSameLenArr(shortArr, 0, k-1, longArr, 0, k-1);}else if (k > longArr.length) {// 后面需要有几个元素int sub = (shortArr.length + longArr.length) - k;int start1 = shortArr.length - 1 - sub;int start2 = longArr.length - 1 - sub;if (longArr[start2] >= shortArr[shortArr.length - 1]) {return longArr[start2];}if (longArr[shortArr.length - 1] <= shortArr[start1]) {return longArr[shortArr.length-1];}return getUpMidFromSameLenArr(shortArr, start1+1, shortArr.length-1, longArr, start2+1, longArr.length-1);}else {int sub = (shortArr.length + longArr.length) - k;// 后面必须凑够20个int start2 = k - shortArr.length - 1;// 排除一个值否则长度不相等if (shortArr[shortArr.length - 1] <= longArr[start2]) {return longArr[start2];}else {start2++;}int end2 = longArr.length - (sub - shortArr.length) - 1;return getUpMidFromSameLenArr(shortArr, 0, shortArr.length-1, longArr, start2, end2);}}/*** 从两个数组中相同长度的子数组部分中求上中位数* @param arr1* @param start1* @param end1* @param arr2* @param start2* @param end2* @return*/private static int getUpMidFromSameLenArr(int[] arr1, int start1, int end1, int[] arr2, int start2, int end2) {int mid1 = 0;int mid2 = 0;while (start1 < end1) {// 获取中间值mid1 = (start1 + end1)/2;mid2 = (start2 + end2)/2;if (arr1[mid1] == arr1[mid2]) {return arr1[mid1];}else {// 计算长度偶数或者奇数,偶数0,奇数1int offset = ((end1 - start1 + 1) & 1) ^ 1;if (arr1[mid1] > arr2[mid2]) {// 奇数的话不需要调整数组大小直接割end1 = mid1;start2 = mid2 + offset;}else {start1 = mid1 + offset;end2 = mid2;}}}return Math.min(arr1[start1], arr2[start2]);}/*** 比较出来两个数组的长短* @param arr1* @param arr2* @return compareRes[0] 为短数组*/private static int[][] compareArr(int[] arr1, int[] arr2) {return arr1.length > arr2.length ? new int[][]{arr2, arr1} : new int[][]{arr1, arr2};}public static void main(String[] args) {System.out.println(findKMinFromSortArrCp1(new int[]{1,2,3}, new int[]{3,4,5,6}, 6));}
c语言版本
正在学习中
c++语言版本
正在学习中
思考感悟
这道题最后分析的地方为什么能够恰好是10呢?这个我仔细想了一下
首先 长数组的起始位置 k-10
结束位置,27-((37-k)-10) = k
那么结束位置 - 起始位 = 10 = 短数组长度
写在最后
方案和代码仅提供学习和思考使用,切勿随意滥用!如有错误和不合理的地方,务必批评指正~
如果需要git源码可邮件给2260755767@qq.com
再次感谢左大神对我算法的指点迷津!
相关文章:
【算法】【算法杂谈】两个排序数组中找第k小的数
目录 前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本 思考感悟写在最后 前言 当前所有算法都使用测试用例运行过,但是不保证100%的测试用例,如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识! 问题介…...

ABAP 新语法--Open SQL(草稿)
1. 常量 1.1 常量赋值 常量字段可以用来为内表中的部分字段赋初始值,字段类型和长度依据输入常量的值决定 SELECTmara~matnr, " 物料号mara~matkl, " 物料组mara~mtart, " 物料类型 AS lkenz, " 删除标识,常量空字符串123 AS fla…...
2023最新常用开发网站汇总
1、在线画图工具 • 在线画图工具ProcessOn:https://www.processon.com/ • 在线画图工具draw.io:https://app.diagrams.net/ • 在线思维导图工具:http://www.mindline.cn/webapp • PlantUML在线编辑器:http://haha98k.com/…...

ELK 日志采集使用
1.安装ELK整体环境 1.1.安装docker环境 Docker 最新版Version 20.10安装_docker最新版本是多少_猿小飞的博客-CSDN博客 1.2.先安装docker compose 安装docker compose_猿小飞的博客-CSDN博客 1.3.使用 Docker Compose 搭建 ELK 环境 1.3.1.编写 docker-compose.yml 脚本启…...
深入剖析RocketMQ源码:消息传递的奥秘
RocketMQ是一款高性能、高可靠性、可扩展性强的分布式消息中间件,能够有效架构企业级分布式应用。由于其广泛应用和优秀表现,越来越多的开发者对RocketMQ的底层实现产生了浓厚的兴趣。本文将深入剖析RocketMQ的消息传递奥秘,帮助大家了解RocketMQ的底层实现原理,进一步掌握…...
Protocol https not supported or disabled in libcurl
原因 curl默认安装完后是只支持http协议而不支持https协议的。 curl -V查看当前curl支持哪些协议: [rootlocalhost /]# curl -V curl 7.19.4 (x86_64-unknown-linux-gnu) libcurl/7.19.4 OpenSSL/1.0.2k zlib/1.2.11 Protocols: tftp ftp telnet dict http fil…...

一步步搭建基于 ts + express + prisma + mongodb + zod 后端服务
环境: windows11、node 18.16.0 、pnpm 1、在合适位置,代开 vscode , 终端执行 mkdir miaooo-backend && cd miaooo-backend && npm init -y 。 创建一个名为一个 miaooo-backend 的项目,并且进入项目 执行 npm 默认初始化。…...

深入理解深度学习——Transformer:编码器(Encoder)部分
分类目录:《深入理解深度学习》总目录 Transformer中的编码器不止一个,而是由一组 N N N个编码器串联而成。一个编码器的输出作为下一个编码器的输入。在下图中有 N N N个编码器,每一个编码器都从下方接收数据,再输出给上方。以此…...

【图像处理】基于收缩系数的粒子群优化和引力搜索算法的多级图像阈值研究【CPSOGSA】(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...

PortSwigger web缓存中毒(Cache Poisoning)
一、什么web缓存中毒? Web缓存中毒(Web Cache Poisoning)是一种攻击技术,攻击者通过操纵Web应用程序的缓存系统,将恶意或欺骗性内容注入到合法的缓存中,以欺骗用户或绕过安全控制。 Web缓存中毒的原理是利用…...

msf渗透练习-生成木马控制window系统
说明: 本章内容,仅供学习,不要用于非法用途(做个好白帽) (一)生成木马 命令: msfvenom -p windows/meterpreter/reverse_tcp LHOST192.168.23.46 LPORT4444 -e x86/shikata_ga_nai -…...

【c++】组合类+继承情况下构造顺序
组合类继承情况下构造顺序 构造顺序同普通继承,先父后子,内部类是最老的(最先调用构造的)。 示例代码 class A { public:A(int a 0):_a(a){cout << "A()" << endl;}~A(){cout << "~A()" …...

盛元广通生物化学重点实验室化学品信息化安全管理系统
生物化学重点实验室是国家基础研究和高技术研究的重要基地,是培养和造就高层次创新型人才的重要基地。为保障实验室化学品安全使用,实验人员可通过现场或移动端管理系统实现化学品安全使用与存储。盛元广通生物化学重点实验室化学品信息化安全管理系统具…...
1.知识积累
(1)build_chain.sh 脚本: build_chain.sh 脚本是 FISCO BCOS 提供的一个工具脚本,用于自动化构建 FISCO BCOS 联盟链。它可以帮助您快速搭建和配置多节点的区块链网络。 具体而言,build_chain.sh 脚本的作用包括以下…...
20230612----重返学习-函数式编程-数据类型检测-网络层优化
day-090-ninety-20230612-函数式编程-数据类型检测-网络层优化 函数式编程 函数式编程 && 命令式编程 函数式编程:把具体的操作过程“封装”到一个函数中,我们无需关注内部是如何处理的(How),只需要关注处理的结果(What)即可; // 如果是依次迭代数组每一项,…...
Java实现删除txt第一行
如果您的文件很大,则可以使用以下方法在不使用临时文件或将所有内容加载到内存中的情况下执行删除. public static void removeFirstLine(String fileName) throws IOException { RandomAccessFile raf new RandomAccessFile(fileName, "rw"); …...
Go语言函数式编程库samber/lo
Go语言函数式编程库samber/lo 开发中,我们经常遇到一些操作,比如获取一个map的所有key,所有value,判断一个字符串是否出现在slice 中,slice中是否有重复元素等等。Go语言没有这样的操作,标准库也不提供。…...
自定义杰理AC63系列BLE数据发送函数
自定义BLE数据发送函数,就是将数据发送、数据发送前的检查、以及conn_handle查询等封装在一起,脱离SDK中的相关回调函数,在程序任意位置实现发送数据功能。 1. SDK中的BLE数据发送函数 BLE的数据发送函数定义在apps\common\third_party_pro…...

Jenkins结合gitee自动化部署SpringBoot项目
安装 安装教程 插件选择 Gitee Plugin 配置 源码管理 填写源码地址 注意:请确保genkins所在的服务器有权限git拉取远程仓库代码,如果不可以请参考ssh配置centos 配置ssh拉取远程git代码 源码管理 构建触发器 1.勾选Gitee webhook 触发构建 2.生成we…...
声强级和声压级之间的转换举例
声强级和声压级之间的转换举例 在学习声学时候,经常会遇到声强级和声压级的概念,而且它们的单位都是分贝(dB),很容易混淆这两个概念。而且,更容易在计算时候,不知如何转换,如何使用,本文将举例说明两者之间…...

python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

PPT|230页| 制造集团企业供应链端到端的数字化解决方案:从需求到结算的全链路业务闭环构建
制造业采购供应链管理是企业运营的核心环节,供应链协同管理在供应链上下游企业之间建立紧密的合作关系,通过信息共享、资源整合、业务协同等方式,实现供应链的全面管理和优化,提高供应链的效率和透明度,降低供应链的成…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Hive 存储格式深度解析:从 TextFile 到 ORC,如何选对数据存储方案?
在大数据处理领域,Hive 作为 Hadoop 生态中重要的数据仓库工具,其存储格式的选择直接影响数据存储成本、查询效率和计算资源消耗。面对 TextFile、SequenceFile、Parquet、RCFile、ORC 等多种存储格式,很多开发者常常陷入选择困境。本文将从底…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的
修改bug思路: 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑:async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...