Shopee SG 前端面试算法题

[YadongZhang]

一面：

Itersection of Multiple Arrays

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]

Input: nums = [[1,2,3],[4,5,6]]
Output: []

实现一个时间复杂度为 O(n) 的算法

[ChevalierLxc]

[[3,1,2,4,5],[1,2,3,4],[3,4,5,6]].toString().split(',')
这样展开成一个 array?

[leokino]

子数组如果元素不重复直接计数然后刷一遍找出现三次的。如果元素重复就保持两个数组。都是 O(n) 的，很简单。然后一般面试不让泄题的，不过这种题无所谓吧。

[B3C933r4qRb1HyrL]

这么简单？

[leokino]

@leokino 三次 -> 对应次数

[neilyoone]

不知道前端用不用 python, python 很好解.

[wd]

循环然后建一个 map 计数就行了，最后一个数组的时候看看 map 和数组数量比较下

[Wongbrah]

nums.reduce((result, currentArray) => result.filter(num => currentArray.includes(num)))

[NathanInMac]

@Wongbrah 老哥你自己数数你这个复杂度是多少

[Araell]

怎么想都是 O(n * m) 啊

[bzw875]

```
const getItersection = (arr) => {
const result = [];
for (let i in arr[0]) {
const tmp = arr[0][i];
let has = 1;
for (let j = 1; j < arr.length; j++) {
if (arr[j].includes(tmp)) {
has++;
}
}
if (has === arr.length) {
result.push(tmp);
}
}
return result;
};
```

[zhengjian]

每个数组无重复用哈希表？

https://runkit.com/notzheng/itersection-of-multiple-arrays

[zhengjian]

好吧，原来是 LeetCode 2248 ，刚提交通过了，😂

https://leetcode.com/problems/intersection-of-multiple-arrays/solution/by-nehzil-9383/

[YARU]

上周周赛第一题
https://leetcode.com/problems/intersection-of-multiple-arrays/

[rioshikelong121]

这个 N 其实指的应该是总的元素个数对吧。 说下思路吧。
循环同时维护一个数据结构 (Map. Object) 以元素为 key 进行计数不就行了。

```javascript
function interaction(arrays){

const counter = {};

for (let i = 0; i < arrays.length; i++) {
const array = arrays[i];
//avoid repeated count in one array.
const cache = {};

for (let j = 0; j < array.length; j++) {
const element = array[j];

if (!(element in counter)) {
counter[element] = 1;
} else if (!(element in cache)) {
counter[element] += 1;
cache[element] = true;
}

}
}


return Object.entries(counter).filter((v, i) => (v[1] >= arrays.length)).map((v) => v[0]);

}


```

[richardwong]

/**
*
* @param {number[][]} nums
* @return {number[]}
*/
var intersection = function (nums) {
let res = [];
// pojo {} 对象的 key 顺序默认是有序的，而 map 的 key 顺序，是按其 set 的顺序来的
// 所以这里使用 {} 而非 new Map()
const map = {};
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums[i].length; j++) {
// 根据题意，内层数组已经去重过
const ele = nums[i][j];
let count = map[ele];
if (count > 0) {
// 记录每个元素出现的次数
map[ele] = ++count;
} else {
map[ele] = 1;
}
}
}
// 出现次数跟外层数组长度一致，即为交集中的元素
Object.keys(map).forEach((el) => {
if (map[el] === nums.length) {
res.push(el);
}
});
return res;
};

作者：YUFENGWANG
链接： https://leetcode-cn.com/problems/intersection-of-multiple-arrays/solution/by-yufengwang-776k/
来源：力扣（ LeetCode ）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

[CookCoder]

求交集么

[rongchuan]

挺简单的...碰到这个题只能说运气太好...

[rongchuan]

@rongchuan
js 在代码这里，不谢，多刷刷题吧...
/**
* @param {number[][]} nums
* @return {number[]}
*/
var intersection = function(nums) {
const m =nums.length;
const arr=nums.flat();
const map =new Map();
const result =[];
for(let i =0;i<arr.length;i++){
map.set(arr[i],map.has(arr[i])? map.get(arr[i])+1:1);
if(map.get(arr[i])===m)
result.push(arr[i])
}
result.sort((a,b)=>a-b);
return result;
};

[YadongZhang]

@rongchuan

空间换时间

[jackbrother]

你运气真好