两个数组的交集 II
2024-08-31 16:10:21
题纲
给定两个数组,编写一个函数来计算它们的交集。
示例 :
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明:
- 输出结果中每个元素出现的次数,应与元素在两个数组中出现的次数一致。
- 我们可以不考虑输出结果的顺序。
方法1:
这种方法原则上比较暴力对所有的数都进行了一次遍历比较,同时清空了对比数组中当前对比相同的值,以防重复检测
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) { var arr = []; for(var i=0;i<nums1.length;i++){ for(var j=0;j<nums2.length;j++){ if(nums1[i] === nums2[j]) {
arr.push(nums1[i])
nums2[j]=null;
break;
} } } return arr; };
方法二:
这个方法是在做完方法一以后想到的优化方法
方法一在两个对比数组基数大了以后需要循环的次数成指数上升,
方法二 则使用一个对象作为中间存储变量,将其中一个作为参照的数组映射入对象中,
以数组的值为KEY,对象值是这个映射进去的数组key在数组中出现的次数,
再循环对比数组去取obj中是否有这个key有则说明相同,将该key的值减一,以此类推
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) { var arr = [],
obj = {}; for(var i=0;i<nums1.length;i++){ if(obj[nums1[i]]){
obj[nums1[i]] = obj[nums1[i]]+1
}else{
obj[nums1[i]] = 1;
}
} for(var j=0;j<nums2.length;j++){ if(obj[nums2[j]]) {
arr.push(nums2[j]);
obj[nums2[j]] = obj[nums2[j]]-1;
} } return arr; };
方法三
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
var intersect = function(nums1, nums2) { var arr = []; nums1.forEach(item=>{
let a = nums2.indexOf(item);
if(a>-1){
arr.push(item)
nums2[a] = null
}
}) return arr; };
进阶:
- 如果给定的数组已经排好序呢?你将如何优化你的算法?
- 如果 nums1 的大小比 nums2 小很多,哪种方法更优?
- 如果 nums2 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?
最新文章
- div悬浮
- 进入meta模式关闭背光灯
- atitit 点播系统 概览 v2 qb1.docx
- 初用protobuf-csharp-port
- NOIP200003方格取数
- Android应用开发高效工具集1---ant构建简单Android项目
- Android设计模式系列
- fastjson将bean转成字符串时首字母变小写问题
- Linux下查看显示器输出状态以及修改显示器工作模式(复制 or 扩展)
- Juniper srx防火墙NAT配置
- 1.Redis 的安装
- angular4.0配置本机IP访问项目
- MyOD-Linux od命令的实现
- LVM : 快照
- Mysql忘记数据库密码以及用户授权案例展示
- 第一次java测试有感
- win7 powershell配色方案
- TortoiseSVN 只取下或更新部分文件的方法(Sparse Update/Sparse Checkout)
- C++11 类型推导decltype
- JavaWeb基础—数据库连接池DBCP、C3P0
热门文章
- IntelliJ IDEA多屏后窗口不显示问题解决(用工具一键解决)
- mac下使用java测试iOS推送
- A Full Hardware Guide to Deep Learning深度学习电脑配置
- vs2015 项目调试出现未能加载文件或程序集“Antlr3.Runtime”或它的某一个依赖项。找到的程序集清单定义与程序集引用不匹配。 (异常来自 HRESULT:0x80131040)
- android --------System.err: java.net.UnknownServiceException: CLEARTEXT .....
- 支付宝小程序开发——H5跳转到小程序(获取小程序页面的链接)
- 【WPF】修改ListBox的Item的样式
- ubuntu apt-get 安装jdk
- cisco路由器telnet及设置用户名和密码的几种方式
- SDN实验---Ryu的应用开发(二)Learning Switch