349 - 两个数组的交集(intersection-of-two-arrays)

Create by jsliang on 2019-07-23 10:11:48
Recently revised in 2019-07-23 11:40:16

一 目录

不折腾的前端,和咸鱼有什么区别

目录
一 目录
二 前言
三 解题
3.1 题解 - Set
3.2 题解 - Map

二 前言

返回目录

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

示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。

三 解题

返回目录

小伙伴可以先自己在本地尝试解题,再回来看看 jsliang 的解题思路。

3.1 解法 - Set

返回目录

  • 解题代码
var intersection = function(nums1, nums2) {
  return [...new Set(nums1.filter(item => new Set(nums2).has(item)))];
};
  • 执行测试

  • nums1[4, 9, 5]

  • nums2[9, 4, 9, 8, 4]
  • return
[ 4, 9 ]
  • LeetCode Submit
✔ Accepted
  ✔ 60/60 cases passed (312 ms)
  ✔ Your runtime beats 5.95 % of javascript submissions
  ✔ Your memory usage beats 5.11 % of javascript submissions (40 MB)
  • 知识点

  • filter()filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。filter() 详细介绍

  • SetSet 对象允许你存储任何类型的唯一值,无论是原始值或者是对象引用。Set 详细介绍

  • 解题思路

最差的 Submit,可能出自最简洁的代码。

  1. 取交集:nums1.filter(item => new Set(nums2).has(item))
  2. 去重:[...new Set(arr)]

这样,就可以取到去重的两个数组的交集,从而完成解题。

3.2 解法 - Map

返回目录

  • 解题代码
var intersection = function(nums1, nums2) {
  let map = new Map();
  let result = [];
  for (let i = 0; i < nums1.length; i++) {
    map.set(nums1[i], i);
  }
  for (let j = 0; j < nums2.length; j++) {
    if (map.get(nums2[j]) !== undefined && result.indexOf(nums2[j]) === -1) {
      result.push(nums2[j]);
    }
  }
  return result;
};
  • 执行测试

  • nums1[4, 9, 5]

  • nums2[9, 4, 9, 8, 4]
  • return
[ 4, 9 ]
  • LeetCode Submit
✔ Accepted
  ✔ 60/60 cases passed (72 ms)
  ✔ Your runtime beats 97.22 % of javascript submissions
  ✔ Your memory usage beats 26.87 % of javascript submissions (35.2 MB)
  • 知识点

  • Map:保存键值对。任何值(对象或者原始值) 都可以作为一个键或一个值。Map 详细介绍

  • push()push() 方法将一个或多个元素添加到数组的末尾,并返回该数组的新长度。push() 详细介绍
  • indexOf():判断数组中是否存在判断条件中的值。如果存在,则返回第一次出现的索引;如果不存在,则返回 -1。indexOf() 详细介绍

  • 解题思路

既然前面使用了内置函数 Set,那么再推荐下 Map 无可厚非。

Map 作为 JS 的内置函数,可用来做哈希表的题解。

在本题中,我们将 nums1 的值,都存储到 Map 中。

然后,遍历 nums2,如果 Map 中包含这个元素,并且数组 result 中不存在这个元素,我们就将它存入到数组中。

最后,根据前面的步骤,我们做到了去重 + 取交集。

  • 进一步思考

使用 Map 或者 Set 肯定不是唯一的两个解,还有更多的其他解,就需要小伙伴个人挖掘了~


不折腾的前端,和咸鱼有什么区别!

图

jsliang 会每天更新一道 LeetCode 题解,从而帮助小伙伴们夯实原生 JS 基础,了解与学习算法与数据结构。

扫描上方二维码,关注 jsliang 的公众号,让我们一起折腾!

知识共享许可协议
jsliang 的文档库梁峻荣 采用 知识共享 署名-非商业性使用-相同方式共享 4.0 国际 许可协议进行许可。
基于https://github.com/LiangJunrong/document-library上的作品创作。
本许可协议授权之外的使用权限可以从 https://creativecommons.org/licenses/by-nc-sa/2.5/cn/ 处获得。

Copyright © jsliang.top 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-23 11:40:46

results matching ""

    No results matching ""