题纲

  给定两个数组,编写一个函数来计算它们的交集。

示例 :

输入: 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 的元素存储在磁盘上,磁盘内存是有限的,并且你不能一次加载所有的元素到内存中,你该怎么办?

最新文章

  1. div悬浮
  2. 进入meta模式关闭背光灯
  3. atitit 点播系统 概览 v2 qb1.docx
  4. 初用protobuf-csharp-port
  5. NOIP200003方格取数
  6. Android应用开发高效工具集1---ant构建简单Android项目
  7. Android设计模式系列
  8. fastjson将bean转成字符串时首字母变小写问题
  9. Linux下查看显示器输出状态以及修改显示器工作模式(复制 or 扩展)
  10. Juniper srx防火墙NAT配置
  11. 1.Redis 的安装
  12. angular4.0配置本机IP访问项目
  13. MyOD-Linux od命令的实现
  14. LVM : 快照
  15. Mysql忘记数据库密码以及用户授权案例展示
  16. 第一次java测试有感
  17. win7 powershell配色方案
  18. TortoiseSVN 只取下或更新部分文件的方法(Sparse Update/Sparse Checkout)
  19. C++11 类型推导decltype
  20. JavaWeb基础—数据库连接池DBCP、C3P0

热门文章

  1. IntelliJ IDEA多屏后窗口不显示问题解决(用工具一键解决)
  2. mac下使用java测试iOS推送
  3. A Full Hardware Guide to Deep Learning深度学习电脑配置
  4. vs2015 项目调试出现未能加载文件或程序集“Antlr3.Runtime”或它的某一个依赖项。找到的程序集清单定义与程序集引用不匹配。 (异常来自 HRESULT:0x80131040)
  5. android --------System.err: java.net.UnknownServiceException: CLEARTEXT .....
  6. 支付宝小程序开发——H5跳转到小程序(获取小程序页面的链接)
  7. 【WPF】修改ListBox的Item的样式
  8. ubuntu apt-get 安装jdk
  9. cisco路由器telnet及设置用户名和密码的几种方式
  10. SDN实验---Ryu的应用开发(二)Learning Switch