问一个题，求相同元素最多的两个数组# JobHunting - 待字闺中
k*g
1 楼
自己想出来的，就假设数组们都是已排序了的吧
比如
A: 1,3,5,7,9,11,20
B: 2,3,5,7,10,11,100
C: 0,3,4,7,12,28,90
则返回A,B，因为他们之间有4个元素相同
比如
A: 1,3,5,7,9,11,20
B: 2,3,5,7,10,11,100
C: 0,3,4,7,12,28,90
则返回A,B，因为他们之间有4个元素相同
f*u
2 楼
这个就是longest common substring吧?
【在 k***g 的大作中提到】
: 自己想出来的，就假设数组们都是已排序了的吧
: 比如
: A: 1,3,5,7,9,11,20
: B: 2,3,5,7,10,11,100
: C: 0,3,4,7,12,28,90
: 则返回A,B，因为他们之间有4个元素相同
【在 k***g 的大作中提到】
: 自己想出来的，就假设数组们都是已排序了的吧
: 比如
: A: 1,3,5,7,9,11,20
: B: 2,3,5,7,10,11,100
: C: 0,3,4,7,12,28,90
: 则返回A,B，因为他们之间有4个元素相同
k*g
3 楼
不一定吧
比如
A: 10 20 30 40 50 60 70
B: 10 22 30 44 50 66 70
C: 11 12 13 14 50 66 70
AB相同的有4个，BC相同的有3个，但longest common substring是BC最长
【在 f*****u 的大作中提到】
: 这个就是longest common substring吧?
比如
A: 10 20 30 40 50 60 70
B: 10 22 30 44 50 66 70
C: 11 12 13 14 50 66 70
AB相同的有4个，BC相同的有3个，但longest common substring是BC最长
【在 f*****u 的大作中提到】
: 这个就是longest common substring吧?
f*u
4 楼
说错了，不是substring，是subsequence，longest common subsequence，经典的dp问
题。
【在 k***g 的大作中提到】
: 不一定吧
: 比如
: A: 10 20 30 40 50 60 70
: B: 10 22 30 44 50 66 70
: C: 11 12 13 14 50 66 70
: AB相同的有4个，BC相同的有3个，但longest common substring是BC最长
题。
【在 k***g 的大作中提到】
: 不一定吧
: 比如
: A: 10 20 30 40 50 60 70
: B: 10 22 30 44 50 66 70
: C: 11 12 13 14 50 66 70
: AB相同的有4个，BC相同的有3个，但longest common substring是BC最长
k*g
5 楼
LCS是不错的想法，不过为了简化问题，我已经假设数组都是排了序的，直接两个指针
向前移动就行了吧？
主要是不太清楚怎样处理多个数组的情况
比如A,B,C,D,E,F... 我的想法是搞两个vector，一个存两个数组名字，比如A,B或者C,
F，另一个存相同元素数量。但这样复杂度是O(m^2) (m是数组数量)
还有更好的办法吗？
【在 f*****u 的大作中提到】
: 说错了，不是substring，是subsequence，longest common subsequence，经典的dp问
: 题。
向前移动就行了吧？
主要是不太清楚怎样处理多个数组的情况
比如A,B,C,D,E,F... 我的想法是搞两个vector，一个存两个数组名字，比如A,B或者C,
F，另一个存相同元素数量。但这样复杂度是O(m^2) (m是数组数量)
还有更好的办法吗？
【在 f*****u 的大作中提到】
: 说错了，不是substring，是subsequence，longest common subsequence，经典的dp问
: 题。
w*w
6 楼
search for min-hash
y*3
7 楼
我觉得可以先把数组变成链表，链表的每个Node保存其对应数组的下标和数值，然后用
一个最小化堆保存每个链表head node。
不断的弹出堆顶元素并且根据前后弹出来的堆顶元素的数值统计两两数组的相同元素个
数。
一个最小化堆保存每个链表head node。
不断的弹出堆顶元素并且根据前后弹出来的堆顶元素的数值统计两两数组的相同元素个
数。
y*a
8 楼
subsequece 有顺序，楼主这个没有顺序。
【在 f*****u 的大作中提到】
: 说错了，不是substring，是subsequence，longest common subsequence，经典的dp问
: 题。
m*n
9 楼
又是国旗那道题的变种。
这种题不是有标准解法了吗？
O(M*N) + O(M*Log(M)) + O(M)
N是数组的个数，M是数组的长度。
【在 k***g 的大作中提到】
: 自己想出来的，就假设数组们都是已排序了的吧
: 比如
: A: 1,3,5,7,9,11,20
: B: 2,3,5,7,10,11,100
: C: 0,3,4,7,12,28,90
: 则返回A,B，因为他们之间有4个元素相同
这种题不是有标准解法了吗？
O(M*N) + O(M*Log(M)) + O(M)
N是数组的个数，M是数组的长度。
【在 k***g 的大作中提到】
: 自己想出来的，就假设数组们都是已排序了的吧
: 比如
: A: 1,3,5,7,9,11,20
: B: 2,3,5,7,10,11,100
: C: 0,3,4,7,12,28,90
: 则返回A,B，因为他们之间有4个元素相同
p*2
10 楼
val a = Vector(1,3,5,7,9,11,20)
val b = Vector(2,3,5,7,10,11,100)
val c = Vector(0,3,4,7,12,28,90)
val aa = Vector(a,b,c)
(for(i_3) last
val b = Vector(2,3,5,7,10,11,100)
val c = Vector(0,3,4,7,12,28,90)
val aa = Vector(a,b,c)
(for(i_3) last
w*w
11 楼
能做到这个 那你就牛了。
【在 m*****n 的大作中提到】
: 又是国旗那道题的变种。
: 这种题不是有标准解法了吗？
: O(M*N) + O(M*Log(M)) + O(M)
: N是数组的个数，M是数组的长度。
【在 m*****n 的大作中提到】
: 又是国旗那道题的变种。
: 这种题不是有标准解法了吗？
: O(M*N) + O(M*Log(M)) + O(M)
: N是数组的个数，M是数组的长度。
v*o
12 楼
求教哪个国旗题？
又是国旗那道题的变种。这种题不是有标准解法了吗？O(M*N) O(M*Log(M)) O(M)N
是数组的个数，M是数组的长度。
【在 m*****n 的大作中提到】
: 又是国旗那道题的变种。
: 这种题不是有标准解法了吗？
: O(M*N) + O(M*Log(M)) + O(M)
: N是数组的个数，M是数组的长度。
又是国旗那道题的变种。这种题不是有标准解法了吗？O(M*N) O(M*Log(M)) O(M)N
是数组的个数，M是数组的长度。
【在 m*****n 的大作中提到】
: 又是国旗那道题的变种。
: 这种题不是有标准解法了吗？
: O(M*N) + O(M*Log(M)) + O(M)
: N是数组的个数，M是数组的长度。
f*u
13 楼
同问
)N
【在 v********o 的大作中提到】
: 求教哪个国旗题？
:
: 又是国旗那道题的变种。这种题不是有标准解法了吗？O(M*N) O(M*Log(M)) O(M)N
: 是数组的个数，M是数组的长度。
)N
【在 v********o 的大作中提到】
: 求教哪个国旗题？
:
: 又是国旗那道题的变种。这种题不是有标准解法了吗？O(M*N) O(M*Log(M)) O(M)N
: 是数组的个数，M是数组的长度。
相关阅读
请问bloomberg技术电面会问些什么呢？ (转载)请教 简历中的research 经验 该怎么写问个面试题Google phone screen reschedule 怎么这么难阿？申请OPT Extension的Request for Evidence请教 一个工资问题看了下VERMONT的天气，一阵心酸没有EAD卡，短期内不可能有，准备直接非法工作了请问intern job的薪水是可以协商的么？OPT加急已经一个多月了谁有方便的包子机，谢谢请问OPT extension要多长时间才能批下来再贴设计电梯Facebook电面请问，男的面试的时候该用什么包合适？代老婆急问据信请问现在H1B transfer premium从file到拿到reciept要多久？五六个人面试，究竟谁说了算啊，Hiring manager吗？有的OPT好快啊...