在两个有序数组中找整体第k小的数
一、题目
给定两个已经排序的数组(假设按照升序排列),然后找出第K小的数。比如数组A = {1, 8, 10, 20}, B = {5, 9, 22, 110}, 第 3 小的数是 8.。要求时间复杂度O(logN),空间复杂度O(1)。
二、解法
2.1、双指针
- 用两个指针
pa、pb分别指向arr1、arr2。- 在初始状态,两个指针分别指向第一个起始值,即pa = 0, pb = 0。
- 然后,我们开始进行比较,如果A数组的值比B数组的值小, 把A数组的指针pa向前移动,然后再进行比较。
- 每次移动,我们都能够得到当前第 i 小的值(随着pa,pb 的移动,i 会逐渐变大)。
- 比如对于数组A = {1, 8, 10, 20}, B = {5, 9, 22, 110}
- 初始时,pa = 0; pb = 0,因为(A[pa] = 1) < (B[pb] = 5), 所以,第 1 小的值为 1
- 这个时候,我们会把 pa 向右移动,即 pa = 1, 并且 pb 保持不变: pb = 0.
- 然后再次比较A[pa] 和 B[pb] 的值,因为 (A[pa] = 8) > (B[pb] = 5), 所以,第 2 小的值是 5, 然后,我们增加 pb 的值。
- 请注意,如果我们用一个变量来保存当前第 i 小的值 (随着pa, pb的移动,i 的值也会增加,那个变量保存的值也会改变)。那么,当pa + pb = k 的时候,那么那个变量保存的一定是第 k 小的值。
- 这里要注意的是,当一个数组的指针已经“到头”了,这个时候怎么进行越界处理呢?我们这里可以用一个简单的判断语句就可以处理了。
2.2、二分查找

Pa+Pb+1=k;
Pa+Pb=k-1;

A[Pa-1]<B[Pb]&&B[Pb]<A[Pa];
B[Pb-1]<A[Pa]&&A[Pa]<B[Pb];

-
通过上面这段代码,我们实际上是把数组延长了,每个数组多了两个值Integer.MIN_VALUE,Integer.MAX_VALUE
- 这样,当pa = 0 是,我们也可以得到A[pa - 1] 的值:Ai_1 = ((pa == 0) ? Integer.MIN_VALUE : A[pa-1]);
- 当 pa =A.length 时,我们可以得到 A[pa]的值:Ai =(pa == A.length) ? Integer.MAX_VALUE : A[pa]。
-
这样,我们就不用担心越界的问题了。
有了上面的分析,代码就容易写出来了。
- 在程序里,我们设置 pa 的初始值为Math.min(A.length, k - 1)
- 然后,通过增加或者减少pa 的值,来使得 B[pb] < A[pa] && B[pb] > A[pa - 1] 或者A[pa] < B[pb] && A[pa] > B[pb - 1] 成立
- 代码中, delta 指的是 pa 的变化量,每次递归以后,delta的值变成一半。
相关文章:
在两个有序数组中找整体第k小的数
一、题目 给定两个已经排序的数组(假设按照升序排列),然后找出第K小的数。比如数组A {1, 8, 10, 20}, B {5, 9, 22, 110}, 第 3 小的数是 8.。…...
Linux 指令心法(十)`head` 显示文本文件的开头部分
文章目录 命令的概述和用途命令的用法命令行选项和参数的详细说明命令的示例命令的注意事项或提示 命令的概述和用途 head 是一个用于显示文本文件的开头部分的命令。它在 Linux 和 Unix 系统中非常有用,因为它允许用户查看文件的前几行,以便快速预览文…...
前端——Layui的导航栏与tab页联动
一、body <!-- 导航栏 --><div class"layui-side layui-bg-black"><div class"layui-side-scroll"><ul id"nav" class"layui-nav layui-nav-tree" lay-filter"stock"><li class"layui-n…...
一致性哈希算法
普通取模算法 假设我们有三台缓存服务器,用于缓存图片,我们为这三台缓存服务器编号为 0号、1号、2号,现在有3万张图片需要缓存,我们希望这些图片被均匀的缓存到这3台服务器上,以便它们能够分摊缓存的压力。也就是说&a…...
深度学习基础之参数量(3)
一般的CNN网络的参数量估计代码 class ResidualBlock(nn.Module):def __init__(self, in_planes, planes, norm_fngroup, stride1):super(ResidualBlock, self).__init__()print(in_planes, planes, norm_fn, stride)self.conv1 nn.Conv2d(in_planes, planes, kernel_size3, …...
红队专题-从零开始VC++远程控制软件RAT-C/S-[2]界面编写及上线
红队专题 招募六边形战士队员1.课前回顾unicode编码 字符串 2.界面编程(下)对话框重载消息函数更改对话框同步更改 3.服务端上线,下线,以及客户端的资源销毁(上)添加socket 变量添加 socket 消息填补config信息创建线程函数 并运行添加Addhost添加 getIt…...
磁盘满了对日志打印(Logback)的影响
背景 我们生产环境有一个服务半夜报警:磁盘剩余空间不足10%,请及时处理。排查后发现是新上线的一个功能,日志打太多导致的,解决方法有很多,就不赘述了。领导担心报警不及时、或者报警遗漏,担心磁盘满了对线…...
【算法与数据结构】--算法基础--数据结构概述
一、什么是数据结构 数据结构是一种组织和存储数据的方式,它定义了数据之间的关系、操作和存储方式,以便有效地访问和修改数据。数据结构是计算机科学中的一个重要概念,它为处理和管理数据提供了基本框架。数据结构通常包括以下几个重要方面…...
QECon大会亮相产品,全栈测试平台推荐:RunnerGo
最近在gitee上看见一款获得GVP(最有价值开源项目)的测试平台RunnerGo,看他们官网介绍包含了接口测试、性能测试、自动化测试。知道他们有saas版可以试用,果断使用了一下,对其中场景管理和性能测试印象深刻,…...
前端小案例-图片存放在远端服务器
前端小案例-图片存放在远端服务器 项目背景: 一个智能产业园的小程序由于可以控制很多种设备,可能有灯、空调、窗帘等智能设备。 现在面临以下问题: 需要存放很多设备的图标。设备的图标可能会进行修改。 为了解决上面的问题,…...
【鼠标右键菜单添加用VSCode打开文件或文件夹】
鼠标右键菜单添加用VSCode打开文件或文件夹 演示效果如下: 右击文件 或右击文件夹 或在文件夹内空白处右击 方法一:重装软件 重装软件,安装时勾选如图所示方框(如果登录的有账号保存有配置信息可以选择重装软件,…...
【jvm--堆】
文章目录 1. 堆(Heap)的核心概述2. 图解对象分配过程2.1 Minor GC,MajorGC、Full GC2.1 堆空间分代思想2.3 内存分配策略2.4 TLAB(Thread Local Allocation Buffer)2.5 堆空间的参数设置2.6 逃逸分析2.7 逃逸分析&…...
【数据库——MySQL(实战项目1)】(1)图书借阅系统
目录 1. 简述2. 功能3. 数据库结构设计3.1 绘制 E-R 图3.2 创建数据库3.3 创建表3.4 插入表数据 1. 简述 经过前期的学习,我们已经掌握数据库基础操作,因此是时候来做一个实战项目了——图书借阅系统。对于图书借阅系统,相信大家不难想到至少…...
[GXYCTF 2019]Ping Ping Ping题目解析
本题考察的内容是rce绕过,本事过滤的东西不算多也算是比较好绕过 基础看到这种先ping一下试试看 输入127.0.0.1看看有啥东西 有回显说明可以接着往下做 借用RCE漏洞详解及绕过总结(全面)-CSDN博客这个大佬整理的rce绕过 ;A;B无论真假,A与B都执行&…...
HTTP协议的请求协议和响应协议的组成,HTTP常见的状态信息
HTTP协议 什么是协议 协议实际上是某些人或组织提前制定好的一套规范,大家只要都按照这个规范来就可以做到沟通无障碍 HTTP协议是W3C(万维网联盟组织)制定的一种超文本传输通信协议(发送消息的模板和数据的格式),除了传送字符串,还有声音、视频、图片等流媒体等超文本信息 …...
【LeetCode】剑指 Offer Ⅱ 第6章:栈(6道题) -- Java Version
题库链接:https://leetcode.cn/problem-list/e8X3pBZi/ 类型题目解决方案栈的应用剑指 Offer II 036. 后缀表达式模拟 栈 ⭐剑指 Offer II 037. 小行星碰撞分类讨论 栈 ⭐单调栈剑指 Offer II 038. 每日温度单调栈 ⭐剑指 Offer II 039. 直方图最大矩形面积单调栈…...
vue3的element-plus的el-dialog的样式修改无效问题
问题描述 想要修改element-plus的对话框el-dialog中的样式,发现在页面style的scoped属性下,使用:deep深入选择器进行修改是无效的。(vue2下深度选择器是有效的) //无效 :deep(.el-dialog){background-color: transparent; }解决…...
归纳所猜半结论推出完整结论:CF1592F1
https://www.luogu.com.cn/problem/CF1592F1 场上猜了个结论,感觉只会操作1。然后被样例1hack了。然后就猜如果 ( n , m ) (n,m) (n,m) 为1则翻转4操作,被#14hack了。然后就猜4操作只会进行一次,然后就不知道怎么做下去了。 上面猜的结论都…...
WPFdatagrid结合comboBox
在WPF的DataGrid中希望结合使用ComboBox下拉框,达到下拉选择绑定的效果,在实现的过程中,遇到了一些奇怪的问题,因此记录下来。 网上能够查询到的解决方案: 总共有三种ItemSource常见绑定实现方式: 1.ItemS…...
Markdown类图之继承、实现、关联、依赖、组合、聚合总结(十五)
简介: CSDN博客专家,专注Android/Linux系统,分享多mic语音方案、音视频、编解码等技术,与大家一起成长! 优质专栏:Audio工程师进阶系列【原创干货持续更新中……】🚀 人生格言: 人生…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
AspectJ 在 Android 中的完整使用指南
一、环境配置(Gradle 7.0 适配) 1. 项目级 build.gradle // 注意:沪江插件已停更,推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
