【CT】LeetCode手撕—4. 寻找两个正序数组的中位数

目录

  • 题目
  • 1- 思路
  • 2- 实现
    • ⭐4. 寻找两个正序数组的中位数——题解思路
  • 3- ACM 实现


题目

  • 原题连接:4. 寻找两个正序数组的中位数

1- 思路

思路

  • 将寻找中位数 ——> 寻找两个合并数组的第 K 大 (K代表中位数)

实现

  • ① 遍历两个数组 :通过比较两个数组的第 [k/2] 个元素 ,如果 numsA[k/2] < numsB[k/2] 的时候,删除 numsA 的前半部分元素。
  • ② 找剩余的 k/2 个元素

2- 实现

⭐4. 寻找两个正序数组的中位数——题解思路

在这里插入图片描述

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 定义 int n = nums1.length;int m = nums2.length;// 用来将 奇数长度 和 偶数长度合并int left = (n+m+1)/2;int right = (n+m+2)/2;return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))*0.5;}public int getKth(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){int len1 = end1-start1+1;int len2 = end2-start2+1;// 始终让 len1 < len2if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);// 1. 递归终止条件if(len1 == 0 ) return nums2[start2+k-1];if(k==1) return Math.min(nums1[start1],nums2[start2]);// 2. 递归逻辑// 2.1 更新start用于递归:保证尽可能不越界 int i = start1 + Math.min(len1,k/2) -1;int j = start2 + Math.min(len2,k/2) -1;// 2.2 删除逻辑if(nums1[i] > nums2[j]){return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j - start2 + 1));}else{return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));}}
}

3- ACM 实现


public class midNum {public static double twoNumMid(int[] nums1,int[] nums2){int len1 = nums1.length;int len2 = nums2.length;int left = (len1+len2+1)/2;int right = (len1+len2+2)/2;return (getKth(nums1,0,len1-1,nums2,0,len2-1,left)+getKth(nums1,0,len1-1,nums2,0,len2-1,right))*0.5;}// 递归public static int getKth(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){// 找lenint len1 = end1-start1+1;int len2 = end2-start2+1;if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);// 2. 终止条件if(len1 == 0) return nums2[start2+k-1];if(k == 1) return Math.min(nums1[start1],nums2[start2]);// 3.单层递归int i = start1 + Math.min(k/2,len1)-1;int j = start2 + Math.min(k/2,len2)-1;// 删 nums2if(nums1[i]>nums2[j]){return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));}else{return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入数组1的长度");int n = sc.nextInt();int[] nums1 = new int[n];System.out.println("输入数组1元素");for(int i = 0 ; i < n ; i ++){nums1[i] = sc.nextInt();}System.out.println("输入数组2的长度");int m = sc.nextInt();int[] nums2 = new int[m];System.out.println("输入数组2元素");for(int j = 0 ; j < m;j++){nums2[j] = sc.nextInt();}double res = twoNumMid(nums1,nums2);System.out.println("中位数是"+res);}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

如何利用AI撰写短文案获客?分享6大平台和3大步骤!

从去年开始&#xff0c;很多大厂都在裁员&#xff0c;原因就是因为AI的火爆&#xff0c;替代了很多机械式的劳动力。以前很多人可以通过机械式的工作来摸鱼&#xff0c;现在AI完成的效率比人工的要高很多倍。 国内好用的AI平台非常多&#xff0c;有时候也可以使用几个AI平台结合…

如何提高内容生产效率

在当前数字化和信息爆炸的时代&#xff0c;内容生产的需求不断增加&#xff0c;如何提高内容生产效率成为企业面临的重要课题。本文将介绍一种有效的内容生产协同工具——【可瓜】&#xff0c;并详细探讨其在提高内容生产效率方面的优势和实际应用。 内容生产任务进度追踪 传统…

【BUUCTF-PWN】7-[第五空间2019 决赛]PWN5

参考&#xff1a;BUU pwn [第五空间2019 决赛]PWN5 //格式化字符串漏洞 - Nemuzuki - 博客园 (cnblogs.com) 格式化字符串漏洞原理详解_printf 任意内存读取-CSDN博客 32位小端排序&#xff0c;有栈溢出保护 运行效果&#xff1a; 查看main函数 存在格式化字符串漏洞 输…

基于iview.viewUI实现行合并(无限制/有限制合并)【已验证可正常运行】

1.基于iview.viewUI实现行合并&#xff08;列之间没有所属对应关系&#xff0c;正常合并&#xff09; 注&#xff1a;以下代码来自于GPT4o&#xff1a;国内直连GPT4o 只需要修改以下要合并的列字段&#xff0c;就可以方便使用啦 mergeFields: [majorNo, devNam, overhaulAdvic…

嵌入式Linux系统编程 — 6.7 实时信号

目录 1 什么是实时信号 2 sigqueue函数 3 sigpending()函数 1 什么是实时信号 等待信号集只是一个掩码&#xff0c;它并不追踪信号的发生次数。这意味着&#xff0c;如果相同的信号在被阻塞的状态下多次产生&#xff0c;它只会在信号集中被记录一次&#xff0c;并且在信号集…

SLAM 精度评估

SLAM 精度的评估有两个最重要的指标&#xff0c;即绝对轨迹误差&#xff08;ATE&#xff09;和相对位姿误差&#xff08;RPE&#xff09;的 均方根误差&#xff08;RMSE&#xff09;: 绝对轨迹误差:直接计算相机位姿的真实值与 SLAM 系统的估计值之间的差值&#xff0c;首先将…

kubernetes service 服务

1 service作用 使用kubernetes集群运行工作负载时&#xff0c;由于Pod经常处于用后即焚状态&#xff0c;Pod经常被重新生成&#xff0c;因此Pod对应的IP地址也会经常变化&#xff0c;导致无法直接访问Pod提供的服务&#xff0c;Kubernetes中使用了Service来解决这一问题&#…

【Linux】多线程(互斥 同步)

我们在上一节多线程提到没有任何保护措施的抢票是会造成数据不一致的问题的。 那我们怎么办&#xff1f; 答案就是进行加锁。 目录 加锁&#xff1a;认识锁和接口&#xff1a;初始化&#xff1a;加锁 && 解锁&#xff1a;全局的方式&#xff1a;局部的方式&#xff1a…

【SkiaSharp绘图15】SKPath属性详解:边界、填充、凹凸、类型判断、坐标、路径类型

文章目录 SKPath 构造函数SKPath 属性Bounds 边界(宽边界)TightBounds紧边界FillType填充方式IsConcave 是否凹/ IsConvex 是否凸IsEmpty是否为空IsLine是否为线段IsRect是否为矩形IsOval是否为椭圆或圆IsRoundRect是否为圆角矩形Item[] 获取路径的坐标LastPoint最后点的坐标Po…

2024最全软件测试面试八股文(答案+文档+视频讲解)

Part1 1、你的测试职业发展是什么&#xff1f; 测试经验越多&#xff0c;测试能力越高。所以我的职业发展是需要时间积累的&#xff0c;一步步向着高级测试工程师奔去。而且我也有初步的职业规划&#xff0c;前3年积累测试经验&#xff0c;按如何做好测试工程师的要点去要求自…

OrangePi AIpro开发板测评 —— 相机图像获取

&#x1f482; 个人主页: 同学来啦&#x1f91f; 版权: 本文由【同学来啦】原创、在CSDN首发、需要转载请联系博主 &#x1f4ac; 如果文章对你有帮助&#xff0c;欢迎关注、点赞、收藏和订阅专栏哦 文章目录 &#x1f31f; 一、引言&#x1f31f; 二、OrangePi AIpro 简要介绍…

力扣206

题目 给你单链表的头节点 head &#xff0c;请你反转链表&#xff0c;并返回反转后的链表。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5] 输出&#xff1a;[5,4,3,2,1]示例 2&#xff1a; 输入&#xff1a;head [1,2] 输出&#xff1a;[2,1]示例 3&#xff1a; 输…

基于Transformer的端到端的目标检测 | 读论文

本文正在参加 人工智能创作者扶持计划 提及到计算机视觉的目标检测&#xff0c;我们一般会最先想到卷积神经网络&#xff08;CNN&#xff09;&#xff0c;因为这算是目标检测领域的开山之作了&#xff0c;在很长的一段时间里人们都折服于卷积神经网络在图像处理领域的优势&…

【数据库】E-R图、E-R模型到关系模式的转换、关系代数表达式、范式

一、E-R图 1、基本概念 2、实体集之间的联系 3、E-R图要点 &#xff08;1&#xff09;实体&#xff08;型&#xff09;的表示 &#xff08;2&#xff09;E-R图属性的表示 &#xff08;3&#xff09;联系的表示 4、E-R模型的例题 二、E-R模型到关系模式的转换 1、实体型的转换…

使用getline()从文件中读取一行字符串

我们知道&#xff0c;getline() 方法定义在 istream 类中&#xff0c;而 fstream 和 ifstream 类继承自 istream 类&#xff0c;因此 fstream 和 ifstream 的类对象可以调用 getline() 成员方法。 当文件流对象调用 getline() 方法时&#xff0c;该方法的功能就变成了从指定文件…

基于STM32F103C8T6的同步电机驱动-CubeMX配置与IQmath调用

基于STM32F103C8T6的同步电机驱动-CubeMX配置与IQmath调用 一、功能描述: 上位机通过CAN总线实现对电机的运动控制,主要包含三种模式:位置模式、速度模式以及力矩模式。驱动器硬件核心为STM32F103C8T6,带相电压采集电路以及母线电压采集电路。其中供电电压12V。 PWM中心对…

【单片机毕业设计选题24047】-基于阿里云的工地环境监测系统

系统功能: 基于STM32完成 主机&#xff08;阿里云以及oled屏显示位置一&#xff09;&#xff1a;烟雾检测&#xff0c;温湿度检测&#xff0c;噪声检测&#xff0c;且用OLED屏显示&#xff0c;设置阈值&#xff0c;超过报警&#xff08;蜂鸣器&#xff09;。 从机&#xff0…

LeetCode题练习与总结:对链表进行插入排序--147

一、题目描述 给定单个链表的头 head &#xff0c;使用 插入排序 对链表进行排序&#xff0c;并返回 排序后链表的头 。 插入排序 算法的步骤: 插入排序是迭代的&#xff0c;每次只移动一个元素&#xff0c;直到所有元素可以形成一个有序的输出列表。每次迭代中&#xff0c;…

Element中的日期时间选择器DateTimePicker和级联选择器Cascader

简述&#xff1a;在Element UI框架中&#xff0c;Cascader&#xff08;级联选择器&#xff09;和DateTimePicker&#xff08;日期时间选择器&#xff09;是两个非常实用且常用的组件&#xff0c;它们分别用于日期选择和多层级选择&#xff0c;提供了丰富的交互体验和便捷的数据…

【server】nacos 安装

1、本地安装 1.1 nacos官网 Nacos官网| Nacos 配置中心 | Nacos 下载| Nacos 官方社区 | Nacos 官网 git 下载地址&#xff1a;https://github.com/alibaba/nacos/releases 1.2 解压并修改配置 1.2.1 通过properties 修改配置&#xff0c;添加数据库配置 1.2.2 创建数据库&…