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

面试篇-求两个有序数组的交集

题目

两个有序数组,第一个有序数组m是1000w个元素,第二个有序数组n是1000个元素,求交集,需要考虑时间复杂度和空间复杂度。

解题思路

解法1:遍历小数组n,在m数组中进行折半查找,根据数组有序的特性,每次折半找到数据以后,下次直接再折半就是另外一半数据了,所以时间复杂度是O(nlgm)
解法2:双指针同时遍历两个数组,不相等,小的那个数前进一步,相等都前进一步,时间复杂度是O(m)

代码参考:

这里采用折半查找:

public static void main(String[] args) {int[] m = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9};int[] n = new int[]{2, 5};List<Integer> results = Lists.newArrayList();int left = 0;int right = m.length - 1;for (int i = 0; i < n.length; i++) {while (left < right) {int mid = (right + left) / 2;if (n[i] == m[mid]) {results.add(n[i]);left = mid;right = m.length - 1;break;}if (n[i] > m[mid]) {left = mid;}if (n[i] < m[mid]) {right = mid;}}}System.out.println(results);}

思维拓展

遇到有序的数组解题思路,一般会用到折半和双指针的思想。
比如:[10,9,8,6,5,4,11,12,23] 这种两边大中间小的数据如何排序?思路就是用双指针从左右遍历,每次取一个最大的数。

相关文章:

面试篇-求两个有序数组的交集

题目 两个有序数组&#xff0c;第一个有序数组m是1000w个元素&#xff0c;第二个有序数组n是1000个元素&#xff0c;求交集&#xff0c;需要考虑时间复杂度和空间复杂度。 解题思路 解法1&#xff1a;遍历小数组n&#xff0c;在m数组中进行折半查找&#xff0c;根据数组有序…...

Web爬虫-edu_SRC-目标列表爬取

免责声明:本文仅做技术交流与学习... 爬取后,结合暗黑搜索引擎等等进行进一步搜索. edu_src.py import requests, time from bs4 import BeautifulSoup for i in range(1, 20):url fhttps://src.sjtu.edu.cn/rank/firm/0/?page{i}print(f"正在获取第{i}页数据")s …...

云原生周刊:Harbor v2.11 版本发布 | 2024.6.17

开源项目推荐 Descheduler Descheduler 是一个工具&#xff0c;可用于优化 Kubernetes 集群中 Pod 的部署位置。它可以找到可以移动的 Pod&#xff0c;并将其驱逐&#xff0c;让默认调度器将它们重新调度到更合适的节点上。 Prowler Prowler 是一款适用于 AWS、Azure、GCP …...

低版本火狐浏览器报错:class is a reserved identifier

低版本火狐浏览器报错&#xff1a;class is a reserved identifier 原因&#xff1a;react-dnd&#xff0c;dnd-core 等node包的相关依赖有过更新&#xff0c;使得在低版本火狐浏览器中不支持 class 解决方法&#xff1a;在使用webpack打包构建时&#xff0c;编译排除node_modu…...

掌握高等数学、线性代数、概率论所需数学知识及标题建议

在数学的广袤领域中&#xff0c;高等数学、线性代数和概率论作为三大核心分支&#xff0c;不仅在理论研究中占据重要地位&#xff0c;更在实际应用中发挥着举足轻重的作用。为了深入理解和掌握这三门学科&#xff0c;我们需要掌握一系列扎实的数学知识。 高等数学所需数学知识 …...

value_and_grad

value_and_grad 是 JAX 提供的一个便捷函数&#xff0c;它同时计算函数的值和其梯度。这在优化过程中非常有用&#xff0c;因为在一次函数调用中可以同时获得损失值和相应的梯度。 以下是对 value_and_grad(loss, argnums0, has_auxFalse)(params, data, u, tol) 的详细解释&a…...

AI 已经在污染互联网了。。赛博喂屎成为现实

大家好&#xff0c;我是程序员鱼皮。这两年 AI 发展势头迅猛&#xff0c;更好的性能、更低的成本、更优的效果&#xff0c;让 AI 这一曾经高高在上的技术也走入大众的视野&#xff0c;能够被我们大多数普通人轻松使用&#xff0c;无需理解复杂的技术和原理。 其中&#xff0c;…...

Linux系统安装ODBC驱动,统信服务器E版安装psqlodbc方法

应用场景 硬件/整机信息&#xff1a;AMD平台 OS版本信息&#xff1a;服务器e版 软件信息&#xff1a;psqlodbc 12.02版本 功能介绍 部分用户在使用etl工具连接数据库时&#xff0c;需要使用到odbc驱动&#xff0c;下面介绍下服务器e版系统中编译安装此工具的相关过程。 E…...

品牌对电商平台价格的监测流程

在当今的电商时代&#xff0c;品牌商会重点关注众多电商平台&#xff0c;如淘宝、天猫、京东、拼多多、苏宁、小红书、抖音、快手等。之所以这些平台备受瞩目&#xff0c;很大程度上是因为其上的店铺数量众多&#xff0c;情况复杂。如今&#xff0c;无论是品牌的经销商还是非经…...

osgearth提示“simple.earth: file not handled”

在用vcpkg编译完osg和osgearth后&#xff0c;为了验证osgearth编译是否正确&#xff0c;进行测试&#xff0c;模型加载代码如下&#xff1a; root->addChild(osgDB::readNodeFile("simple.earth")); 此时以为是simple.earth路径的问题&#xff0c;遂改为以下代码…...

hbuilderx如何打包ios app,如何生成证书

hbuilderx可以打包ios app, 但是打包的时候&#xff0c;却需要两个证书文件&#xff0c;我们又如何生成这两个证书文件呢&#xff1f; 点击hbuilderx的官网链接&#xff0c;教程是需要使用mac电脑苹果开发者账号去创建这两个文件&#xff0c;可是问题来了&#xff0c;我们没有…...

扩散模型荣获CVPR2024最佳论文奖,最新成果让评估和改进生成模型更加效率!

CVPR 2024最佳论文奖新鲜出炉 其中一篇是Rich Human Feedback for Text-to-Image Generation&#xff0c;受大模型中的RLHF技术启发&#xff0c;团队用人类反馈来改进Stable Diffusion等文生图模型。 作者提出了收集丰富的细粒度人类反馈信息&#xff0c;用于更好地评估和改进…...

通过CSS样式来禁用href

<style>.disabled-link {pointer-events: none;cursor: default;text-decoration: none;color: inherit; }</style><a href"https://www.example.com" class"disabled-link">禁用链接</a> 在上述CSS样式中&#xff0c; pointer-…...

汽车传动系统为汽车动力总成重要组成部分 我国市场参与者数量不断增长

汽车传动系统为汽车动力总成重要组成部分 我国市场参与者数量不断增长 汽车系统主要包括动力系统、制动系统、传动系统、转向系统、行驶系统、燃油供给系统、照明系统以及电器系统。汽车传动系统指能够将发动机产生的动力转化为车辆行驶驱动力的动力传递装置。汽车传动系统为汽…...

智慧校园软件解决方案:提升学校管理效率的最佳选择

在当今教育领域&#xff0c;智慧校园信息化方案正逐渐成为提升学校管理水平与教学品质的关键途径。这一方案融合了最新科技&#xff0c;通过数字化、网络化及智能化方式&#xff0c;全面革新教育资源分配与教育互动模式&#xff0c;旨在为学校带来以下核心价值与优势 1. 综合信…...

数据结构之B数

目录 1.概述 2.特点 3.诞生 4.优缺点 4.1.优点 4.2.缺点 5.应用场景 6.C语言中的B树实现例子 7.总结 1.概述 B树&#xff08;B-tree&#xff09;是一种自平衡的树数据结构&#xff0c;广泛应用于数据库和文件系统中&#xff0c;以便高效地进行顺序读取、写入以及查找…...

计算机基础必须知道的76个常识!沈阳计算机软件培训

01 信息技术是指人们获取、存储、传递、处理、开发和利用信息资源的相关技术。 02 1、计算机的特点&#xff1a; &#xff08;1&#xff09;运算速度快 &#xff08;2&#xff09;存储容量大 &#xff08;3&#xff09;通用性强 &#xff08;4&#xff09;工作自动化 &…...

7,KQM模块的驱动

1&#xff0c;查资料&#xff0c;查模块的通信接口&#xff08;单片机和模块之间采用什么方式通信&#xff09;硬件接口&#xff0c;驱动方式(串口驱动用串口发送接收PC10&#xff0c;PC11) 只用了三个脚&#xff1a;VCC &#xff27;&#xff2e;&#xff24; &#xff34;&…...

软件验收测试报告模版分享,如何获取专业的验收测试报告?

软件验收测试报告是对软件开发过程中的最后一步确认&#xff0c;通过对软件进行全面、系统的检查和测试&#xff0c;形成一份详细的报告&#xff0c;以评估软件是否满足用户需求和设计要求。验收测试报告起到了非常重要的作用&#xff0c;不仅可以帮助开发者了解软件开发的质量…...

【arm扩容】docker load -i tar包 空间不足

背景&#xff1a; 首先我在/home/nvidia/work下导入了一些镜像源码tar包。然后逐个load进去。当我 load -i dev-aarch64-18.04-20210423_2000.tar包的时候&#xff0c;出现 Error processing tar file(exit status 1): write /9818cf5a7cbd5a828600d9a4d4e62185a7067e2a6f2ee…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

进程地址空间(比特课总结)

一、进程地址空间 1. 环境变量 1 &#xff09;⽤户级环境变量与系统级环境变量 全局属性&#xff1a;环境变量具有全局属性&#xff0c;会被⼦进程继承。例如当bash启动⼦进程时&#xff0c;环 境变量会⾃动传递给⼦进程。 本地变量限制&#xff1a;本地变量只在当前进程(ba…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

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

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

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

LOOI机器人的技术实现解析:从手势识别到边缘检测

LOOI机器人作为一款创新的AI硬件产品&#xff0c;通过将智能手机转变为具有情感交互能力的桌面机器人&#xff0c;展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家&#xff0c;我将全面解析LOOI的技术实现架构&#xff0c;特别是其手势识别、物体识别和环境…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一&#xff1a;HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二&#xff1a;Floyd 快慢指针法&#xff08;…...