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) 的算法

目前还没有人写得出来时间复杂度为 O(n) 的算法，哪怕是空间换了时间。

[ChevalierLxc]

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

[leokino]

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

[cuvii]

这么简单？

[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]

你运气真好

[YadongZhang]

目前还没有人写得出来时间复杂度为 O(n) 的算法，哪怕是空间换了时间。

[biubiuF]

如果不含重复元素的话用数组字典就行，时间复杂度就是 o(n)

[rongchuan]

@YadongZhang ...我写的这么简单，就一个 for 循环，这还不是 O(n)啊...我感觉这里你没理解对，可以简单试试，你随便输个测试 case ，debug 看看堆栈，是不是 O(n)。还有一点就是，前端算法面试一般只需要考虑时间就行，没人会让你写限制空间多少的代码的，要考虑空间的话就不可能用 js 写。我这里声明这么多变量就是为了好看，方便面试官看懂这个代码。

[YadongZhang]

@rongchuan

sort 就已经不是 O (n) 了

[rongchuan]

@YadongZhang ...你要这么说的话.flat 就不是 O(n)了，严格来说是 O(3n)，但算法复杂度不算常量的呀....O(3n)还是 O(n)

[YadongZhang]

@rongchuan

js 内置 sort 算法的时间复杂度是 O(n*lgn)，不管是用 Merge Sort 还是 Tim Sort ，所以上述算法的整体时间复杂度应该是 O(n*lgn)，常数这种情况下是可以忽略的

如果有优化的方法，可以用 @richardwong 提到的 obj 来有序遍历，而不是 Map ，最后的结果就不用重新排序了

[rongchuan]

@YadongZhang 这道面试算法是想实现求交集，关键算法是用哈希表这一步，所以他说的复杂度也是指的哈希表这一步的复杂度，而且 js 的 sort 也不一定是 nlogn 。打个比方，一些稍微复杂的算法，会有很多这种类似操作，不是算法核心的点都可以用语法糖写，因为是算法面试，不是在优化系统，也不是算法竞赛（即使是算法竞赛，也是用 c++的一些库来写，同样是语法糖，不过效率高一点），要严格扣的话，可以把这些语法糖代码写在 main 执行函数里，关键代码单独写成函数，那这个函数就是严格 O(n)的了，因为像 leetcode 一类的刷题平台，他是帮你把 main 函数写了，真要是扣到常量级的复杂度，那肯定是你自己写 main 函数，就能这么操作了

[YadongZhang]

@rongchuan

是的，论查找一个元素，HashMap 和 HashSet 的 O (1) 时间复杂度优于数组的线性查找 O(n) 和二分查找 O(lgn)

[4kingRAS]

没细想，不过估计最终大概是个 O （ c*n ）的东西

[metrue]

const intersection = (nums = []) => {
let m = {}
nums.forEach((arr, idx) => {
if (idx === 0) {
arr.forEach((c) => {
m[c] = true
})
} else {
const nm = {}
arr.forEach((c) => {
if (m[c] === true) {
nm[c] = true
}
})
m = nm
}
})
return Object.keys(m)
}


随手写了一下，很丑陋的进行了 object 的 reference 重写.

[zhzy0077]

这题没说要有序 leetcode 的题目要求有序
对于无序输入你要有序输出只能在 O(N)的排序里想法子 如果不对数组数字设限制的话是不可能的 OP 也别想着难倒所有人了

[DonkeyBenjamin]

I don't know how to write js, so here is my first python attempt (which passed)

https://leetcode.com/submissions/detail/692241616/

```python
class Solution:
def intersection(self, nums: List[List[int]]) -> List[int]:
num_count = [0 for _ in range(1000)]
for arr in nums:
for num in arr:
num_count[num-1] += 1

l = len(nums)
result = [i+1 for i in range(1000) if num_count[i] == l]
return result
```

[pigmen]

如果最后不要求顺序的话？比如 3,4 输出为 4,3
O(n) 应该很简单？

[YePiaoling]

@leokino +1
拿数组记一下就可以了

[jayLink]

数组记录下标
```
func intersection(nums [][]int) []int {
arr:=[10001]int{} //数组存储结果不排序
m:=len(nums)
for i:=0;i<len(nums);i++{
for j:=0;j<len(nums[i]);j++{
arr[nums[i][j]]++
}
}

res:=[]int{}
for i,v:=range arr{
if v==m{
res = append(res,i)
}
}
return res
}
```

[zhzbql]

function itersection(nums) {
let indexToNumValue = {}
let len = nums.length
nums.forEach((subArray, subArrayIdx) => {
subArray.forEach(v => {
indexToNumValueV = indexToNumValue[v]
if (indexToNumValueV) {
if (!indexToNumValueV.indexToParent[subArrayIdx]) {
indexToNumValueV.len += 1
indexToNumValueV.indexToParent[subArrayIdx] = 1
}
}
else indexToNumValue[v] = { len: 1, indexToParent: { [subArrayIdx]: 1 } }
})
})
return Object.keys(indexToNumValue).filter(key => indexToNumValue[key].len >= len)
}

[brucep]

计数排序，时间复杂度 O(n)，空间复杂度 O(n)。
上面有朋友给了 lc 的题目链接，数组元素的取值范围和数组长度是一个范围的，符合计数排序的要求

[brucep]

附上代码
/**
* 2248. Intersection of Multiple Arrays
* Solution: Counting Sort
* Time Complexity: O(n)
* Space Complecity: O(n)
* @param {number[][]} nums
* @return {number[]}
*/
var intersection = function(nums) {
const counts = new Array(1000 + 10).fill(0);
for (const numArr of nums) {
for (const num of numArr) {
counts[num]++;
}
}
return counts.map(
(val, idx) => val === nums.length ? idx : 0
).filter(val => val !== 0);
};

[surmon]

一个 Map 不就完了

[jzz7280]

function intersection(nums) {
let repeat = new Set()
let reset = new Set()
const result = []
nums.forEach((item, index) => {
item.forEach(val => {
if (index === 0) {
repeat.add(val)
} else if (repeat.has(val)) {
reset.add(val)
if (index+1 === nums.length) {
result.push(val)
}
}
})
if (index !== 0) {
repeat = reset
reset = new Set()
}
})
return result
}

[tingyunsay]

@surmon 楼主意思是要 O(n)时间复杂度，结果要有序输出，会有一个 sort

[afutureus]

@tingyunsay 不可能啊。

极端情况，输入只有一个列表。

输入无序，输出有序，那么必须经过排序算法。

基于比较的算法 至少 nlogn 。

其它算法，不给数据范围等于耍流氓 :(

[tingyunsay]

@afutureus 有这种情况，他的数字若是限制在 0 ~ n 的，可以申请一个长度为 n 的数组，直接写入到对应的位置标记个 1 ，未写入的为 0 ，最后从 0 到 n 扫描结果，非 0 的加入结果，这样总体是算是 O(2n)，也有序。不过感觉他这题目也没限制...