k***g
发帖数: 166 | 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个元素相同 | f*****u
发帖数: 308 | 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
发帖数: 166 | 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吧?
| f*****u
发帖数: 308 | 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
发帖数: 166 | 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问
: 题。
| w***w
发帖数: 84 | | y**3
发帖数: 12 | 7 我觉得可以先把数组变成链表，链表的每个Node保存其对应数组的下标和数值，然后用
一个最小化堆保存每个链表head node。
不断的弹出堆顶元素并且根据前后弹出来的堆顶元素的数值统计两两数组的相同元素个
数。 | y**********a
发帖数: 824 | 8
subsequece 有顺序，楼主这个没有顺序。
【在 f*****u 的大作中提到】
: 说错了，不是substring，是subsequence，longest common subsequence，经典的dp问
: 题。
| m*****n
发帖数: 2152 | 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个元素相同
| p*****2
发帖数: 21240 | 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<-aa; j<-aa if i!=j) yield (i,j,i.intersect(j).length)) sortBy (_.
_3) last | w***w
发帖数: 84 | 11 能做到这个 那你就牛了。
【在 m*****n 的大作中提到】
: 又是国旗那道题的变种。
: 这种题不是有标准解法了吗？
: O(M*N) + O(M*Log(M)) + O(M)
: N是数组的个数，M是数组的长度。
| v********o
发帖数: 67 | 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是数组的长度。
| f*****u
发帖数: 308 | 13 同问
)N
【在 v********o 的大作中提到】
: 求教哪个国旗题？
:
: 又是国旗那道题的变种。这种题不是有标准解法了吗？O(M*N) O(M*Log(M)) O(M)N
: 是数组的个数，M是数组的长度。
|
|
