Shopee SG 前端面试算法题

nums

input

output

算法

43 条回复 • 2022-05-07 11:06:03 +08:00

1

ChevalierLxc

2022-04-29 18:55:55 +08:00

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

2

leokino

2022-04-29 18:56:04 +08:00

1

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

3

B3C933r4qRb1HyrL

2022-04-29 18:56:17 +08:00

这么简单？

4

leokino

2022-04-29 18:56:31 +08:00

@leokino 三次 -> 对应次数

5

neilyoone

2022-04-29 19:03:04 +08:00

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

6

wd

2022-04-29 19:04:52 +08:00 via iPhone

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

7

Wongbrah

2022-04-29 19:35:09 +08:00

1

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

8

NathanInMac

2022-04-29 19:57:27 +08:00

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

9

Araell

2022-04-29 20:02:49 +08:00 via Android

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

10

bzw875

2022-04-29 20:16:29 +08:00

1

```
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;
};
```

11

zhengjian

2022-04-29 20:25:15 +08:00

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

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

12

zhengjian

2022-04-29 20:25:57 +08:00

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

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

13

YARU

2022-04-29 20:28:23 +08:00

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

14

rioshikelong121

2022-04-29 20:37:41 +08:00

1

这个 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]);

}

```

15

richardwong

2022-04-30 16:00:43 +08:00

1

/**
*
* @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 ）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

16

CookCoder

2022-05-01 15:23:15 +08:00

求交集么

17

rongchuan

2022-05-01 17:34:14 +08:00

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

18

rongchuan

2022-05-01 17:45:28 +08:00

1

@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;
};

19

YadongZhang

OP

2022-05-01 18:05:58 +08:00 via Android

@rongchuan

空间换时间

20

jackbrother

2022-05-02 10:19:21 +08:00

你运气真好

21

YadongZhang

OP

2022-05-02 10:42:13 +08:00

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

22

biubiuF

2022-05-02 11:29:15 +08:00

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

23

rongchuan

2022-05-02 13:11:26 +08:00

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

24

YadongZhang

OP

2022-05-02 13:14:37 +08:00 via Android

2

@rongchuan

sort 就已经不是 O (n) 了

25

rongchuan

2022-05-02 13:23:45 +08:00

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

26

YadongZhang

OP

2022-05-02 13:48:11 +08:00 via Android

@rongchuan

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

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

27

rongchuan

2022-05-02 15:27:32 +08:00

1

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

28

YadongZhang

OP

2022-05-02 17:59:51 +08:00 via Android

@rongchuan

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

29

4kingRAS

2022-05-03 15:13:53 +08:00

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

30

metrue

2022-05-03 16:39:06 +08:00

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 重写.

31

zhzy0077

2022-05-03 17:35:38 +08:00

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

32

DonkeyBenjamin

2022-05-03 19:02:24 +08:00

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
```

33

pigmen

2022-05-04 00:10:33 +08:00

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

34

YePiaoling

2022-05-04 07:49:29 +08:00

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

35

jayLink

2022-05-04 11:41:18 +08:00

数组记录下标
```
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
}
```

36

zhzbql

2022-05-04 16:56:18 +08:00

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)
}

37

brucep

2022-05-05 13:43:23 +08:00

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

38

brucep

2022-05-05 13:49:32 +08:00

附上代码
/**
* 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);
};

39

surmon

2022-05-06 01:56:52 +08:00

一个 Map 不就完了

40

jzz7280

2022-05-06 09:01:54 +08:00

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
}

41

tingyunsay

2022-05-06 16:58:33 +08:00

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

42

afutureus

2022-05-06 21:02:30 +08:00 via iPhone

@tingyunsay 不可能啊。

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

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

基于比较的算法至少 nlogn 。

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

43

tingyunsay

2022-05-07 11:06:03 +08:00

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