每日一练 寻找两个正序数组的中间数

题目参上,以下是解题思路:

首先,我们应该想到的一种方法是把两数组合并为一个整体的数组,然后返回其中位数即可。那么我们如何合并两数组呢?我们可以用归并排序,设置上下两指针,不断遍历返回较小的那个同时指针后移,这样我们就可以把数组合并,同时我们要注意这样的几种特殊情况:

1.nums1和nums2中有空数组

显然,若其中一个为空,我们直接判断另一个的中位数即可。

2.nums1和nums2的长度不一样

这种怎么办呢?我们只需要设置进入数组的长度即可,即若其中一个已经全部进入数组,那么直接把另一个数组的剩余所有数全进入即可。

那么这个思路能否优化一下呢?

首先,我们要注意,我们只是想要找这两数组的中位数,其实并不需要把整个的数组全都和起来,我们只需要找到数组的中位数所在的位置即可,其次,我们的搜寻方法能否优化呢?显然,二分查找就在这里派上了用场。

下面是解题思路:( 作者:windliang  来源:力扣(LeetCode)) 

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n1 = nums1.length ;
        int n2 = nums2.length ;
        int left = ( n1 + n2 + 1 ) / 2 ;
        int right = ( n1 + n2 + 2 ) /2 ;
        return (erFen( nums1 , 0 , n1 - 1 , nums2 , 0 , n2 - 1 , left ) + erFen(nums1 , 0 , n1 - 1 , nums2 , 0 , n2 - 1 , right )) * 0.5 ;//注意不能用 /2
    }
    private int erFen(int[] nums1 , int start1 , int end1 , int[] nums2 , int start2 , int end2 , int key){
        int len1 = end1 - start1 + 1 ;
        int len2 = end2 - start2 + 1 ;//注意是实时长度更新
        if( len1 > len2 ){
            return erFen(nums2 , start2 , end2 , nums1 , start1 , end1 , key) ;//保证len1小于len2,这样如果出现空数组则一定为len1
        }
        if( len1 == 0 ){
            return nums2[start2 + key - 1] ;//注意数组是从0开始的
        }
        if( key == 1){
            return Math.min(nums1[start1] , nums2[start2]) ;
        }
        int i = start1 + Math.min(len1 , key / 2 ) - 1 ;
        int j = start2 + Math.min(len2 , key / 2 ) - 1 ;//找到两标记位置i和j
        if(nums1[ i ] > nums2[ j ]){
           return erFen(nums1 , start1 , end1 , nums2 , j + 1 , end2 , key - ( j - start2 + 1)) ;
        }
        else{
           return erFen(nums1 , i + 1 , end1 , nums2 , start2 , end2 , key - ( i - start1 + 1)) ;
        }
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

字节新作:图像生成质量超越DiT

🌟每日更新最新高质量论文,关注我,时刻关注最新大模型进展。🌟 📌 元数据概览: 标题:Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction作者&#xff1a…

2012年认证杯SPSSPRO杯数学建模C题(第二阶段)碎片化趋势下的奥运会商业模式全过程文档及程序

2012年认证杯SPSSPRO杯数学建模 C题 碎片化趋势下的奥运会商业模式 原题再现: 从 1984 年的美国洛杉矶奥运会开始,奥运会就不在成为一个“非卖品”,它在向观众诠释更高更快更强的体育精神的同时,也在攫取着巨大的商业价值&#…

LeetCode-热题100:21. 合并两个有序链表

题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入: l1 [1,2,4], l2 [1,3,4] 输出: [1,1,2,3,4,4] 示例 2: 输入: l1 [], l2 [] 输出…

什么是ICMP协议,如何防护ICMP攻击

一.什么是ICMP ICMP(Internet Control Message Protocol)是互联网控制报文协议,是TCP/IP协议族的一个子协议。它主要用于在IP网络中传递控制信息和错误消息,是IP协议的补充。ICMP协议是一种无连接协议,它不需要建立…

如何锁定鼠标光标在水平、垂直或45度对角线模式下移动 - 鼠标水平垂直移动锁定器简易教程

在我们进行精细工作例如如创建图标和图形设计时,通常需要我们对鼠标移动进行精确控制。一旦向左或向右轻微移动,都可能导致设计出错。若出现不必要的错误,我们极有可能不得不重新开始,这会令人感到非常沮丧。这种情况下&#xff0…

NIO基础知识

在学习Netty之前先要学习一下NIO相关的知识,因为Netty是基于NIO搭建的一套网络编程框架。 一. NIO 基础 non-blocking io 非阻塞 IO 1. 三大组件 1.1 Channel & Buffer channel 有一点类似于 stream,它就是读写数据的双向通道,可以从…

SSM实战项目——哈哈音乐(三)文件服务器模块开发

1、创建模块 创建一个子模块(hami-fie),里面不写任何代码,专门用于文件上传的服务器 在hami-file的webapp下创建上传文件资源的文件夹,并引入资源(图片、音频) 2、pom.xml主配置文件中引入文件…

提升提测质量之研测共建

提升提测质量之研测共建 简介 你是否也有同样的困惑?跟进的需求,就在提测前一秒,被告知不能如期提测了,研测计划被打乱;提测的功能,犹如遇到不好的购物体验,缺斤短两,与prd预期不符…

Elasticsearch:我们如何演化处理二进制文档格式

作者:来自 Elastic Sean Story 从二进制文件中提取内容是一个常见的用例。一些 PDF 文件可能非常庞大 — 考虑到几 GB 甚至更多。Elastic 在处理此类文档方面已经取得了长足的进步,今天,我们很高兴地介绍我们的新工具 —— 数据提取服务&…

AopContext.currentProxy() 的代理对象错误(未被更新)问题

背景: 原来在springAOP的用法中,只有代理的类才会被切入,我们在controller层调用service的方法的时候,是可以被切入的,但是如果我们在service层 A方法中,调用B方法,切点切的是B方法,…

猫头虎技术分享 || 断网了,还能ping127.0.0.1吗?

博主猫头虎的技术世界 🌟 欢迎来到猫头虎的博客 — 探索技术的无限可能! 专栏链接: 🔗 精选专栏: 《面试题大全》 — 面试准备的宝典!《IDEA开发秘籍》 — 提升你的IDEA技能!《100天精通鸿蒙》 …

开源大语言模型(LLM)汇总(持续更新中)

随着ChatGPT的火爆,越来越多人希望在本地运行一个大语言模型。为此我维护了这个开源大语言模型汇总,跟踪每天不发的大语言模型和精调语言模型。 我将根据个模型采用的基础大模型进行分类,每个大模型下列出各派生模型。 Alpaca (Stanford) 斯…

Java毕业设计 基于SSM jsp商城系统 美妆系统

Java毕业设计 基于SSM jsp商城系统 美妆系统 SSM jsp 商城系统 美妆系统 功能介绍 首页 分类展示商品 搜索商品 登录 注册 邮箱激活 购物车 结算 支付 我的订单 个人信息设置 后台管理 登录 商品管理 添加修改下架商品 商品类型管理 添加修改删除分类 订单管理 确认发货 取消…

SAP HCM 多成本中心薪酬过账标准程序解读

SAP HCM薪酬过账会涉及到CO对象,CO对象主要是成本中心、WBS、内部订单、订单等,成本中心有多个维护地方0001信息类型0027信息类型等,那么成本中心多个地方维护,优先级是如何,0027>1018>0001,也就是说人身上的优先…

微电网优化:基于​海象优化算法(Walrus Optimization Algorithm,WOA)​的微电网优化(提供MATLAB代码)

一、微电网优化模型 微电网是一个相对独立的本地化电力单元,用户现场的分布式发电可以支持用电需求。为此,您的微电网将接入、监控、预测和控制您本地的分布式能源系统,同时强化供电系统的弹性,保障您的用电更经济。您可以在连接…

隐语SecretFlow实训营-第8讲:快速上手隐语SCQL的开发实践

SCQL使用/集成实践 目前SCQL只开放API供用户使用/集成 使用SCDBClient上手体验可以基于SCQL API开发封装白屏产品,或集成到业务链路中 使用流程: 部署系统 环境配置: 机器配置:CPU/MEM最低8C16G机构之间的网络互通 镜像&…

雪球acw_sc__v2 加密参数构造解析

打开雪球网站:https://xueqiu.com/today 首先打开Edge浏览器,清除应用程序里面的cookie 接着,跳转到源代码,刷新网页,进行调试,首先进入debugger模式,需要反debug调试。 输入相关代码,解除subug模式 点击保留日志,这里显示有两次请求,分别分析下。 第一个today返…

重读Java设计模式: 适配器模式解析

引言 在软件开发中,经常会遇到不同接口之间的兼容性问题。当需要使用一个已有的类,但其接口与我们所需的不兼容时,我们可以通过适配器模式来解决这一问题。适配器模式是一种结构型设计模式,它允许接口不兼容的类之间进行合作。本…

AI绘画:使用ComfyUI结合LCM进行实时绘图:开启AI艺术创作新篇章

在数字艺术的世界里,ComfyUI和LCM(Latent Contextual Modulation)的结合为艺术家和设计师们提供了一个强大的实时绘图工具。LCM是一种先进的技术,它能够实时地将用户的输入和反馈融入到图像生成过程中,从而创造出动态变…

Vue3从入门到实战:掌握状态管理库pinia(上部分)

1.新的状态管理工具pinia Pinia 是一个状态管理库&#xff0c;通俗点讲&#xff0c;它的主要作用就是帮助我们在 Vue 3 应用中更好地管理和维护组件的状态。 举例子解释&#xff1a; 新建一个Count.vue文件&#xff0c;功能用来计数求和。 <template><div class&q…