黑车电面+题目代码及探讨

一个小时，上来就是做题，没有自我介绍。题目很有意思，考到的地方也很多，所以贴上来，和地里朋友们讨论讨论。
题目： find common elements in n arrays，
比如：
3 个array
int[] arr1 = {1,2,3,4,5,6,8,10,13};
int[] arr2 = {3,5,7,9,13,14,15};
int[] arr3 = {3,6,9,10,13};

要求返回 3个array都有的 common elems就是 {3, 13}.

方法一：
我上来就跟面试官说用HashSet, 记录arr1的所有，然后遍历arr2, 更新HashSet, set

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

，search要 lgm, 在m > n的情况下不好，在n > m的下更好。

关于代码和复杂度分析， 欢迎大家批评指正。

觉得有用的，请加大米！！谢谢！！



补充内容 (2019-4-5 12:36):
是昨天面的，1小时就这1题。今天拿到onsite。大家加油！

衣领子 发表于 2019-4-5 14:18
粗粗看了一下方法三如果{1112}{3}{4} 貌似会返回1？

面试时没考虑重复的情况。
你说的对，重复的话，放node进heap时候就要检查一下了，重复则check next node。

我觉得可以 先把每个数组排序， 之后找到前两个数组第一个共同元素， 再用移动指针的法方在其他n - 2个 数组中找是否存在该元素。 之后再找前两个数组第二个共同元素， 再在其他n - 2 的数组中找是否存在该元素， 以此类推。 这样的话复杂度应该是O(mn)

wx6807 发表于 2019-4-13 09:43
既然是sorted，直接跟k merge一样从头一个个pop就行了呗，哪一个大就pop哪一个，直到三个都相等？

不是哪个小pop哪个么
同时pop出去的那个数属于哪个list就从那个list再取一个数入堆

感觉应该从最短的那个string入手吧

粗粗看了一下方法三如果{1112}{3}{4} 貌似会返回1？

每一个arry 都是unique 的吗? 也就是common element 只考虑跨多个arr ?

学习网站 散思酒 TwoPointer

say543 发表于 2019-4-5 14:51
每一个arry 都是unique 的吗? 也就是common element 只考虑跨多个arr ?

面试时可以考虑每个都是unique的。common element 定义为跨多个arr 。

这题主要就是对长的array binary search吧，对短的线性扫描

a9lklk 发表于 2019-4-6 00:36
学习网站 散思酒 TwoPointer

yep. but intersection of n arrays.