Shopee SG 前端面试算法题

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

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

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

@rongchuan

sort 就已经不是 O (n) 了

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

@rongchuan

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

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

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

@rongchuan

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

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

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

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

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

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

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

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

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

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

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

一个 Map 不就完了

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
}