facebook 面筋

好吧，巨简单的一道题
LL 原题 interselcection of array
就是给你两个 array 想找相同的 Integer

印度小哥很nice 可以楼主太水，跟小哥讨论了has

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

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

验的。求二面失败。

补充内容 (2016-9-12 05:28):
投投

更正是Leetcode 原题， interselect of array I 和 II 一就是没重复，二是有重复。双指针扫两个数组。如果连个数组有同样元素，输出，如果两个数组有两个同样的也要输出第二遍。真心容易。不让用 set。一开始写出来了。但小哥说你不对啊。一慌就写飞了。不知道最后怎么写了。希望能有个二面。因为真的实在太简单了。我同学知道我考这种题都哭了。说你这都写不出来。铁定挂了。

cicean 发表于 2016-9-9 23:40
忘了说了，已经排号序列了。省了Arrays.sort

若2个数组已sorted，那么用two pointers (O(Na + Nb) time complexity worse case). 这个和设计求vector dot product找两个vector相同的非零分量指标是一个思路。

1. 
   
2. vector<int> findCommon(vector<int>& a, vector<int>& b) {
   
3.   vector<int> res;
   
4.   int ia = 0, ib = 0, na = a.size(), nb = b.size();
   
5.   while (ia < na && ib < nb) {
   
6.     if (a[ia] == b[ib]) {
   
7.       res.push_back(a[ia]); ia++; ib++; // output if a common found
   
8.     }
   
9.     else if (a[ia] > b[ib]) ib++; // b[ib] is behind, let its index catch up a little
   
10.     else ia++;                          // a[ia] is behind, let its index catch up a little
    
11.   }
    
12.   return res;
    
13. }
    

复制代码

数组是排好序的吗？

没排序的排好序然后双指针+Set？lz是不是就差了一点？有重复的话至少结果要用Set存吧

已经说出了解法。
然后进行了深入讨论。
不用多想。会有的。

重复是指重复元素不论重复几遍，输出结果也必须要输出相应的重复次数个是吗？如果没有重复元素，可以先把长度的小的数组排序，然后线性扫另外一个数组，每次用binary search找重复元素。有重复就不知道怎么做了。。。

iPhD 发表于 2016-9-9 09:34
重复是指重复元素不论重复几遍，输出结果也必须要输出相应的重复次数个是吗？如果没有重复元素，可以先把长 ...

https://discuss.leetcode.com/top ... ion-without-hashset

有重复的话 排个序也可以通过双指针做出来的吧？

eko910817 发表于 2016-9-9 23:39
有重复的话 排个序也可以通过双指针做出来的吧？

忘了说了，已经排号序列了。省了Arrays.sort

eko910817 发表于 2016-9-9 23:39
有重复的话 排个序也可以通过双指针做出来的吧？

但排序了时间复杂度就大了呀