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

[tingyunsay]

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

[afutureus]

@tingyunsay 不可能啊。

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

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

基于比较的算法 至少 nlogn 。

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

[tingyunsay]

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