Repository navigation
腾讯&leetcode：给定两个数组，编写一个函数来计算它们的交集 #6
Description
Activity
const fn = (n1,n2)=>[...new Set(n1.filter(i => n2.includes(i)))]; console.log(fn([1,2,2,1],[2,2]))Reacted by gd, jiazhangyao, Beanactor and Aqiu!用Map是O(n)的时间
var intersection = function(nums1, nums2) { const map = {}, ans = []; nums1.forEach(element => { map[element] = true; }); nums2.forEach(element => { if (map[element]) { ans.push(element); } }); return ans; }
Reacted by JoshuaTao and fasengReacted by zhenglong0034var intersection = function(nums1, nums2) { let map1 = new Set(nums1); let map2 = new Set(nums2); let res = [] map1.forEach((item) => { if(map2.has(item)){ res.push(item) } }) return res };const getIntersection = (nums1, nums2) => { return Array.from(new Set(nums1.filter(item => !!~nums2.indexOf(item)))); }
Reacted by JetReacted by supershutong, Tmac-1 and liuyu/*找交集*/ function intersection(arr1, arr2){ var hash = {}, _intersection = [] for(let ele of arr1){ if(!hash.hasOwnProperty(ele)){ hash[ele] = true } } for(let ele of arr2){ if(hash[ele]){ var flag = false // NaN标志 if(_intersection.indexOf(ele) === -1){ if(ele !== ele){ if(!flag){ flag = true _intersection.push(ele) } }else{ _intersection.push(ele) } } } } return _intersection } console.log(intersection([1,2,2,1], [2,2])) // [2] console.log(intersection([4,9,5], [9,4,9,8,4])) // [9,4] console.log(intersection([4,9,5,NaN], [9,4,9,8,4,NaN])) // [9,4,NaN] /*找并集*/ function union(arr1,arr2){ return Array.from(new Set([...arr1, ...arr2])) } console.log(union([1,2,2,1], [2,2])) // [1,2] console.log(union([4,9,5], [9,4,9,8,4])) // [4,9,5,8] console.log(union([4,9,5,NaN], [9,4,9,8,4,NaN])) // [4,9,5,NaN,8] /*找差集*/ function difference(arr1, arr2){ var set1 = new Set(arr1) var set2 = new Set(arr2) for(let ele of set1){ if(set2.has(ele)){ set2.delete(ele) } } return Array.from(set2) } console.log(difference([1,2,2,1], [2,2])) // [] console.log(difference([4,9,5], [9,4,9,8,4])) // [8] console.log(difference([4,9,5,NaN], [9,4,9,8,4,NaN])) // [8]
Reacted by PoisonSnowFlyingvar fn = (nums1, nums2) => { var small = nums1, big = nums2; if (nums1.length > nums2.length) { small = nums2; big = nums1; } return Array.from(new Set(small.filter(t => big.indexOf(t) > -1))); }; console.log(fn([1, 2, 2, 1], [2, 2])) // [2] console.log(fn([4,9,5], [9,4,9,8,4])) // [4,9]var fn = (nums1, nums2) => { var small = nums1, big = nums2; if (nums1.length > nums2.length) { small = nums2; big = nums1; } return small.filter(t => big.indexOf(t) > -1); }; fn([1, 2, 3, 4], [2, 6])这个好像不满足
fn([1,2,3,4], [2,2]) // [2,2]
var fn = (nums1, nums2) => { var small = nums1, big = nums2; if (nums1.length > nums2.length) { small = nums2; big = nums1; } return small.filter(t => big.indexOf(t) > -1); }; fn([1, 2, 3, 4], [2, 6])这个好像不满足
fn([1,2,3,4], [2,2]) // [2,2]
改了，没注意去重
function getIntersection(arr1, arr2) { var arr = []; arr1.forEach(function(elem) { arr2.includes(elem) && !arr.includes(elem) && arr.push(elem); }) return arr; }function intersection(arr1, arr2) { if( arr1 instanceof Array && arr2 instanceof Array ){ return Array.from(new Set(arr1.filter(item=>new Set(arr2).has(item)))); } throw 'What I need are two arrays'; }@WeCheung 你这filter里面，每一次都要new Set一遍，虽然代码简写了，但浪费了很多资源
@597796340 多谢提醒
function intersection(arr1, arr2) { if( arr1 instanceof Array && arr2 instanceof Array ){ const set = new Set(arr2); return Array.from(new Set(arr1.filter(item=>set.has(item)))); } throw 'What I need are two arrays'; }
function combineArr(arr1,arr2) { let res=arr1.filter((item)=> arr2.includes(item)) return new Set(res) }- changed the title
[-]leetcode：给定两个数组，编写一个函数来计算它们的交集[/-][+]leetcode349：给定两个数组，编写一个函数来计算它们的交集[/+]on Apr 8, 2020 4 remaining items
/** * 查找 arr1与arr2之间的交集 * @param {*} arr1 * @param {*} arr2 */ const sameItem = (arr1, arr2) => arr1.filter((i) => arr2.includes(i)); const arr1 = [1, 2, 3, 4, 2, 1]; const arr2 = [3, 4, 5, 6, 3, 4]; console.log(sameItem(arr1, arr2)); // [3, 4]
用Map是O(n)的时间
var intersection = function(nums1, nums2) { const map = {}, ans = []; nums1.forEach(element => { map[element] = true; }); nums2.forEach(element => { if (map[element]) { ans.push(element); } }); return ans; }
没去重哦
去重很简单，第二个for循环判断map中存在元素之后，ans的push之后将其删除即可
var intersection = function(nums1, nums2) { var result = []; var set1 = new Set([...nums1]); var set2 = new Set([...nums2]); for (var i of set2) { if (set1.has(i)) { result.push(i); } } return result; };
// set 的方案 /** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection = function(nums1, nums2) { var result = []; var smallerSet = new Set(nums1); var biggerSet = new Set(nums2); if(biggerSet.size < smallerSet.size){ var temp = smallerSet; smallerSet = biggerSet; biggerSet = temp; } smallerSet.forEach((item) => { if(biggerSet.has(item)){ result.push(item); } }); return result; };
Accepted
- 60/60 cases passed (72 ms)
- Your runtime beats 60.86 % of javascript submissions
- Your memory usage beats 83.33 % of javascript submissions (34.1 MB)
var intersection = function (nums1, nums2) { const map = {}, ans = [] nums1.forEach((element) => { if (!map[element]) map[element] = 1 }) nums2.forEach((element) => { if (map[element]) { map[element]++ if (map[element] == 2) { ans.push(element) } } }) return ans }
用Map是O(n)的时间
var intersection = function(nums1, nums2) { const map = {}, ans = []; nums1.forEach(element => { map[element] = true; }); nums2.forEach(element => { if (map[element]) { ans.push(element); } }); return ans; }
这样的写法会导致最终的ans数组包含重复元素噢
- changed the title
[-]leetcode349：给定两个数组，编写一个函数来计算它们的交集[/-][+]腾讯&leetcode：给定两个数组，编写一个函数来计算它们的交集[/+]on Jan 31, 2021 题目地址(349. 两个数组的交集)
https://leetcode-cn.com/problems/intersection-of-two-arrays/
题目描述
给定两个数组，编写一个函数来计算它们的交集。 示例 1： 输入：nums1 = [1,2,2,1], nums2 = [2,2] 输出：[2] 示例 2： 输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出：[9,4] 说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。前置知识
- hashtable
公司
- 阿里
- 腾讯
- 百度
- 字节
思路
先遍历第一个数组，将其存到 hashtable 中，然后遍历第二个数组，如果在 hashtable 中存在就 push 到 ret，然后清空 hashtable，最后返回 ret 即可。
关键点解析
- 空间换时间
代码
代码支持：JS, Python
Javascript Code:
/** * @param {number[]} nums1 * @param {number[]} nums2 * @return {number[]} */ var intersection = function (nums1, nums2) { const visited = {}; const ret = []; for (let i = 0; i < nums1.length; i++) { const num = nums1[i]; visited[num] = num; } for (let i = 0; i < nums2.length; i++) { const num = nums2[i]; if (visited[num] !== undefined) { ret.push(num); visited[num] = undefined; } } return ret; };
Python Code:
class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: visited, result = {}, [] for num in nums1: visited[num] = num for num in nums2: if num in visited: result.append(num) visited.pop(num) return result # 另一种解法：利用 Python 中的集合进行计算 def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: return set(nums1) & set(nums2)
复杂度分析
- 时间复杂度：$O(N)$
- 空间复杂度：$O(N)$
更多题解可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
Reacted by luciferReacted by lucifer用Map是O(n)的时间
var intersection = function(nums1, nums2) { const map = {}, ans = []; nums1.forEach(element => { map[element] = true; }); nums2.forEach(element => { if (map[element]) { ans.push(element); } }); return ans; }
你这个有问题啊，已经推进去的元素，会出现重复的元素，我改了一下，多加一个map 存储已经推进去的元素即可避免重复
const UnionTwoArray = (arr1: number[], arr2: number[]) => { const map1: Record<number, boolean> = {}; const map2: Record<number, boolean> = {}; const result: number[] = []; arr1.forEach(item => { map1[item] = true; }); arr2.forEach(item => { if (map1[item] && !map2[item]) { result.push(item); map2[item] = true; } }); return result; };
function intersection(nums1: number[], nums2: number[]): number[] { return nums1.reduce((pre: number[], cur: number) => { if (nums2.includes(cur) && !pre.includes(cur)) { pre.push(cur); } return pre; }, []); }
function mixed (nums1,nums2) { return nums1.reduce((prev,cur) => { if (nums2.includes(cur)) { prev.push(cur) } return [...new Set(prev)]; },[]) }
function intersection(nums1: number[], nums2: number[]): number[] { let res = [] for(let i = 0; i< nums1.length; i++) { if(nums2.includes(nums1[i]) && !res.includes(nums1[i])) { res.push(nums1[i]) } } return res };- 这是来自QQ邮箱的假期自动回复邮件。你好，我最近正在休假中，无法亲自回复你的邮件。我将在假期结束后，尽快给你回复。
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
示例 2:
说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
附leetcode地址：leetcode