当前位置: 首页 > 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] 这种两边大中间小的数据如何排序?思路就是用双指针从左右遍历,每次取一个最大的数。

http://www.lryc.cn/news/377543.html

相关文章:

  • Web爬虫-edu_SRC-目标列表爬取
  • 云原生周刊:Harbor v2.11 版本发布 | 2024.6.17
  • 低版本火狐浏览器报错:class is a reserved identifier
  • 掌握高等数学、线性代数、概率论所需数学知识及标题建议
  • value_and_grad
  • AI 已经在污染互联网了。。赛博喂屎成为现实
  • Linux系统安装ODBC驱动,统信服务器E版安装psqlodbc方法
  • 品牌对电商平台价格的监测流程
  • osgearth提示“simple.earth: file not handled”
  • hbuilderx如何打包ios app,如何生成证书
  • 扩散模型荣获CVPR2024最佳论文奖,最新成果让评估和改进生成模型更加效率!
  • 通过CSS样式来禁用href
  • 汽车传动系统为汽车动力总成重要组成部分 我国市场参与者数量不断增长
  • 智慧校园软件解决方案:提升学校管理效率的最佳选择
  • 数据结构之B数
  • 计算机基础必须知道的76个常识!沈阳计算机软件培训
  • 7,KQM模块的驱动
  • 软件验收测试报告模版分享,如何获取专业的验收测试报告?
  • 【arm扩容】docker load -i tar包 空间不足
  • 基于PID的直流电机自动控制系统的设计【MATLAB】
  • MySQL----事务
  • 客观评价,可道云teamOS搭建的企业网盘,如Windows本地电脑一般的使用体验真的蛮不错
  • 当页面中有多个echarts图表的时候,resize不生效的修改方法
  • connect-caption-and-trace——用于共同建模图像、文本和人类凝视轨迹预测
  • iOS API方法弃用警告说明及添加
  • canvas绘制红绿灯路口(二)
  • Semantic Kernel 直接调用本地大模型与阿里云灵积 DashScope
  • 【人工智能】深度解读 ChatGPT基本原理
  • 【教程】2024年如何快速提取爆款视频的视频文案?
  • 【MySQL连接器(Python)指南】02-MySQL连接器(Python)版本与实现