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

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

目录

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


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

1- 思路

题目识别

  • 识别1 :给定两个数组 nums1nums2 ,找出数组的中位数

二分

思路

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

实现

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

其实现思路在于,始终让 nums1 为元素数量少的数组


2- 实现

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

在这里插入图片描述

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {// 1. 长度int len1 = nums1.length;int len2 = nums2.length;// 定义 right// 排除奇、偶 影响int left = (len1+len2+1)/2;int right = (len1+len2+2)/2;return ((findK(nums1,0,len1-1,nums2,0,len2-1,left) + findK(nums1,0,len1-1,nums2,0,len2-1,right))*0.5);}public int findK(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){// 始终让 nums2 最长int len1 = end1 - start1+1;int len2 = end2 - start2+1;if(len1>len2) return findK(nums2,start2,end2,nums1,start1,end1,k);// 判断if(len1==0) return nums2[start2+k-1];if(k == 1) return Math.min(nums1[start1],nums2[start2]);// 递归逻辑int i = start1 + (Math.min(len1,k/2)-1);int j = start2 + (Math.min(len2,k/2)-1);if(nums1[i] > nums2[j]){return findK(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));}else{return findK(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));}}
}

3- ACM 实现

public class findM {public static double findMid(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 ((findK(nums1,0,len1-1,nums2,0,len2-1,left) + findK(nums1,0,len1-1,nums2,0,len2-1,right))*0.5);}private static double findK(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){// 递归终止int len1 = end1 - start1 + 1;int len2 = end2 - start2 + 1;if(len1>len2) return findK(nums2,start2,end2,nums1,start1,end1,k);// 终止if(len1==0) return nums2[start2+k-1];if(k == 1) return Math.min(nums1[start1],nums2[start2]);// 递归int i = start1 + (Math.min(len1,k/2)-1);int j = start2 + (Math.min(len2,k/2)-1);if(nums1[i] > nums2[j]){return findK(nums1,start1,end1,nums2,j+1,end2,k - (j-start2+1));}else{return findK(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);String input = sc.nextLine();input = input.replace("[","").replace("]","");String input2 = sc.nextLine();input2 = input2.replace("[","").replace("]","");String[] parts = input.split(",");int[] nums = new int[parts.length];for(int i = 0 ; i < nums.length;i++){nums[i] = Integer.parseInt(parts[i]);}String[] parts2 = input2.split(",");int[] nums2 = new int[parts.length];for(int i = 0 ; i < nums2.length;i++){nums2[i] = Integer.parseInt(parts2[i]);}System.out.println("结果是"+findMid(nums,nums2));}
}

相关文章:

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

目录 1- 思路题目识别二分 2- 实现⭐4. 寻找两个正序数组的中位数——题解思路 3- ACM 实现 原题链接&#xff1a;4. 寻找两个正序数组的中位数 1- 思路 题目识别 识别1 &#xff1a;给定两个数组 nums1 和 nums2 &#xff0c;找出数组的中位数 二分 思路 将寻找中位数 —…...

【LLM text2sql】浅看大模型用于text2sql的综述

前言 之前笔者分享了text2sql & LLM & KG的有机结合实现KBQA的问答&#xff0c; 《【LLM & RAG & text2sql】大模型在知识图谱问答上的核心算法详细思路及实践》、 《【开源分享】KBQA核心技术及结合大模型SPARQL查询生成问答实践》。 我们再来看看大模型在te…...

Node js介绍

目录 概要**对Node的认识****Node的概念理解****Node和浏览器区别****Node的架构图** **Node的应用场景****Node的安装****安装Node的LTS版本****Node的版本管理工具nvm(了解)** **Node的输入和输出**Node程序传递参数Node的输出 **Node的全局对象****特殊的全局对象****其他的…...

企业编辑抖音百科词条有什么用?

企业编辑抖音百科词条有什么用&#xff1f; 百科词条创建对企业&#xff0c;品牌以及个人的重要性&#xff01;#百科词条创建#百科营销#百科词条费用# 企业编辑百科词条主要是有以下这些好处&#xff0c;首先是丰富企业在网络上的信息&#xff0c;提高企业的知名度。 百科词条…...

数据结构-链式二叉树-四种遍历

博客主页&#xff1a;【夜泉_ly】 本文专栏&#xff1a;【数据结构】 欢迎点赞&#x1f44d;收藏⭐关注❤️ 数据结构-链式二叉树-四种遍历 1.前言2.前、中、后序遍历2.1前序遍历2.1中、后序遍历 3.层序遍历3.1递归实现3.2队列实现关于在Pop之后为什么还能用tmp访问节点&#x…...

【YashanDB知识库】数据库获取时间和服务器时间不一致

本文转自YashanDB官网&#xff0c;具体内容可见数据库获取时间和服务器时间不一致 【问题分类】功能使用 【关键字】服务器时间、数据库时间 【问题描述】数据库获取的时间和服务器时间不一致。 【问题原因分析】YashanDB并没有时区的概念&#xff0c;数据库的时间以数据库启…...

十大排序之:冒泡排序

目录 一、简介 实现过程 时间复杂度 二、代码实现 函数声明 Swap函数 单趟 多趟 测试 优化 一、简介 冒泡排序是一种简单的排序算法&#xff0c;它重复地比较相邻的两个元素&#xff0c;如果顺序错误就交换它们&#xff0c;直到没有元素需要交换为止。这个过程类…...

【MPC】无人机模型预测控制复现Data-Driven MPC for Quadrotors项目(Part 1)

无人机模型预测控制复现Data-Driven MPC for Quadrotors项目 参考链接背景和问题方法与贡献实验结果安装ROS创建工作空间下载RotorS仿真器源码和依赖创建Python虚拟环境下载data_driven_mpc仓库代码下载并配置ACADO求解器下载并配置ACADO求解器的Python接口下载并配置rpg_quadr…...

微信小程序开发——比较两个数字大小

在这里我们使用的工具是 需要自行安装和配置。 在微信小程序中比较两个数字大小有以下几种方式&#xff1a; 一、普通条件判断 在小程序的.js 文件中&#xff0c;先定义两个数字&#xff0c;如let num1 5; let num2 3;。通过if - else if - else语句&#xff0c;根据num1与…...

Java多线程3

1.有序性在并发编程中的含义。 有序性在并发编程中指的是在多线程环境下&#xff0c;程序的执行顺序应与单线程情况下保持一致&#xff0c;以避免出现不确定或错误的执行结果。 2.为何需要使用多线程进行程序设计&#xff1f; 使用多线程可以提高程序的效率&#xff0c;利用…...

node+Vue项目环境创建

nodeVue项目环境创建 使用淘宝镜像源使用官方镜像源()清除缓存取消取消ssl验证安装vue 使用淘宝镜像源 npm config set registry https://registry.npm.taobao.org/使用官方镜像源() 由于国内网络问题&#xff0c;安装报错 npm install -g cnpm --registryhttps://registry.…...

云智AI人工智能平台——与众不同之处

人工智能领域、深度学习、强化学习、大小模型盛行的时代&#xff0c;人工智能技术正以前所未有的速度改变着我们的世界。然而&#xff0c;在众多AI平台中&#xff0c;如何选择一个既高效又灵活的工具&#xff0c;成为了每个开发者心中的难题。今天&#xff0c;我们特别介绍一款…...

国庆节有什么好物值得入手?精选国庆节必选好物合集

一年一度的国庆节马上来临了&#xff0c;平时舍不得买的好物可以在国庆节这段时间大采购了&#xff0c;毕竟这可是年度购物的好时机&#xff0c;千万不要错过这个享受优惠的机会。还不知道买什么国庆节好物的朋友可以看看本篇文章&#xff0c;提前做好功课噢&#xff01; 好物…...

并发安全与锁

总述 这篇文章&#xff0c;我想谈一谈自己对于并发变成的理解与学习。主要涉及以下三个部分&#xff1a;goroutine&#xff0c;channel以及lock 临界区 首先&#xff0c;要明确下面两组概念 并发和并行 并行&#xff1a;指几个程序每时每刻都同时进行 并发&#xff1a;指…...

细胞分裂检测系统源码分享

细胞分裂检测检测系统源码分享 [一条龙教学YOLOV8标注好的数据集一键训练_70全套改进创新点发刊_Web前端展示] 1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 项目来源AACV Association for the Advancement of Computer Vis…...

openssl 生成多域名 多IP 的数字证书

openssl.cnf 文件内容&#xff1a; [req] default_bits 2048 distinguished_name req_distinguished_name copy_extensions copy req_extensions req_ext x509_extensions v3_req prompt no [req_distinguished_name] countryName CN stateOrProvinceName GuangDong l…...

电影评论|基于springBoot的电影评论网站设计与实现(附项目源码+论文+数据库)

私信或留言即免费送开题报告和任务书&#xff08;可指定任意题目&#xff09; 目录 一、摘要 二、相关技术 三、系统设计 四、数据库设计 五、核心代码 六、论文参考 七、源码获取&#xff1a; 一、摘要 随着信息技术在管理上越来越深入而广泛的应用&#xff0c…...

【C++】虚函数

一、什么是虚函数 在类的成员函数前加上virtual关键字&#xff0c;这个函数就是虚函数。 虚函数的所用就是完成多态。多态示例如下&#xff1a; class A {public:virtual void func()//虚函数{cout << "A" << endl;}void ftwo()//普通函数{cout <&…...

esxi虚拟机启用cbt备份(增量备份)

在虚拟机中启用CBT 1.关闭虚拟机。 右键点按虚拟机&#xff0c;Edit Settings-VM Options-Advanced-Configuration Parameters-Edit Configuration- Add parameters&#xff0c;添加ctkEnabled参数&#xff0c;并将其值设置为true。 Add parameters&#xff0c;添加scsi0:0…...

mysql 8.0 时间维度表生成(可运行)

文章目录 mysql 8.0 时间维度表生成实例时间维度表的作用时间维度表生成技术细节使用时间维度表的好处 mysql 8.0 时间维度表生成实例 时间维度表的作用 dim_times&#xff08;时间维度表&#xff09;在数据仓库&#xff08;Data Warehouse&#xff09;中的作用至关重要。作为…...

【Linux】shell脚本忽略错误继续执行

在 shell 脚本中&#xff0c;可以使用 set -e 命令来设置脚本在遇到错误时退出执行。如果你希望脚本忽略错误并继续执行&#xff0c;可以在脚本开头添加 set e 命令来取消该设置。 举例1 #!/bin/bash# 取消 set -e 的设置 set e# 执行命令&#xff0c;并忽略错误 rm somefile…...

前端倒计时误差!

提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

【HTML-16】深入理解HTML中的块元素与行内元素

HTML元素根据其显示特性可以分为两大类&#xff1a;块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态

前言 在人工智能技术飞速发展的今天&#xff0c;深度学习与大模型技术已成为推动行业变革的核心驱动力&#xff0c;而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心&#xff0c;系统性地呈现了两部深度技术著作的精华&#xff1a;…...