这是一个创建于 3413 天前的主题，其中的信息可能已经有所发展或是发生改变。
任意两个时间序列：
比如
A： 3,4,5, 7,8,910, 18,19
B: 4,5, 16,17,18,19,20，
输出
4,5 18,19
比如
A： 3,4,5, 7,8,910, 18,19
B: 4,5, 16,17,18,19,20，
输出
4,5 18,19
 |
1
zhengnanlee 2015-07-19 23:48:15 +08:00 via Android
最长公共子序列？
|
 |
2
lixia625 2015-07-19 23:49:49 +08:00
print [i for i in B if i in A]
|
 |
3
wy315700 2015-07-19 23:52:03 +08:00
线段树吧
|
 |
4
aheadlead 2015-07-20 00:13:11 +08:00
随便找个查找树吧…
|
 |
5
ariestiger 2015-07-20 00:15:36 +08:00
你这是有间断的两个时间序列，问题就不应该是你这样的。
本质上就是 Range 之间的交，差运算了。 之前做交易系统时，在订单发生退货退款时，要计算订单从下单到现在“真正”用了多少时间（也就是要把发生退货退款处理的时间段排队掉，而一个订单生命周期中可能发生多次退货退款，因为有的退货退款可能会被拒绝，用户后面可以继续申请退货退款），从而决定是不是要执行相应的定时任务。 因为 Java 里没有像 Ruby, Python 里的 Range 类，只能自己写个类来做一下了。 这个计算主要就是一个主线时间段，从订单最后更新时间到现在，另一个是若干退货退款的时间段（发生时间到结束时间），写个方法，循环，对每个退货退款时间段，看它和主线时间段的关系（其实主线时间段肯定是包含退货退款时间段的，不然就异常了），然后进行相减就行了。 你这里的话，主线时间段可以就用[min(A), max(A)]，需要排队的支线时间段，从 A 和 B 中去提取，自己去考虑间隔点的问题了，然后做 Range 之间的运算就好了。 |
 |
6
meteor2013 OP @zhengnanlee 不是最长公共子序列，是所有公共子序列
|
 |
7
clink8001 2015-07-20 00:28:41 +08:00
用python 可以这么做：
a = [3,4,5, 7,8,910, 18,19 ] b = [ 4,5, 16,17,18,19,20] h = filter(lambda f: f in a, b) print h |
 |
8
messyidea 2015-07-20 00:31:20 +08:00 via Android
线段树蛮方便的
|
 |
9
iloahz 2015-07-20 00:35:29 +08:00
时间序列是不是可以认为可以有序啊，排好序两个指针跑一遍？
|
 |
10
SoloCompany 2015-07-20 00:57:06 +08:00
题目没说清楚，那么久成了遍准求交集问题
set(A).retainAll(set(B)) 完事 （（ |
 |
11
tushiner 2015-07-20 01:01:47 +08:00
看了九章算法的广告，只看标题以为楼主和他们是一路的
|
 |
12
sciooga 2015-07-20 01:12:56 +08:00 via Android
有序的？
睡前随便想了一下 Python 应该是这样写比较快吧？ A = [3, 4, 5, 7, 8, 9, 10, 18, 19] B = [4, 5, 16, 17, 18, 19, 20] b_index = 0 b_end_index = len(B) for i in A: ....while(b_index<b_end_index): ........if B[b_index] > i: ............break ........elif B[b_index] == i: ............print i ............break ........b_index += 1 |
|
13
meteor2013 OP @iloahz 对，是有序的
|
|
14
meteor2013 OP |
 |
15
msg7086 2015-07-20 01:47:58 +08:00
时间序列是什么？
时间点？ 时间段？ 题目好乱根本读不明白…… |
 |
16
linxy 2015-07-20 01:48:50 +08:00 via Android
区间查找一般都是线段树。
|
|
17
meteor2013 OP @msg7086
A： 3,4,5, 7,8,9，10, 18,19 => A序列的子序列有3-5， 7-10和18-19 B: 4,5, 16,17,18,19,20，=> B有4-5，和 16-20两个子序列 => A和B相同的重叠部分就是：4-5和 18-19两段。 |
|
18
msg7086 2015-07-20 03:29:00 +08:00
@meteor2013 性能好点的用线段树，性能差点的用归并比较。
我不懂前者。 |
 |
19
mangocool 2015-07-20 08:58:25 +08:00
算法，咱不懂，学习！
|
|
20
messyidea 2015-07-20 09:04:14 +08:00
我感觉如果输入有序，且每个点都输入而不只输入时间段的起始和结束的话只需要扫一遍就可以了，复杂度O(2n), 如果是n个时间序列，要求覆盖m遍及以上的时间段，可以用线段树来处理。 说实话只有两个时间段用线段树小题大做了。
|
 |
21
iker01 2015-07-20 09:30:45 +08:00
一般用线段树解决区间问题。
|
|
22
meteor2013 OP @iker01 能举个例子具体说说吗？
|
|
23
meteor2013 OP @iker01 还有就是线段树一般处理无序序列，这个是有序的，能减少复杂度吗？
|
 |
24
likuku 2015-07-20 10:01:18 +08:00
python
使用 set (集合) 类型一步搞定： # & 交集 >>> print ( set([4, 5, 16, 17, 18, 19, 20]) & set([3, 4, 5, 7, 8, 9, 10, 18, 19])) set([18, 19, 4, 5]) |
 |
25
RisingV 2015-07-20 10:05:23 +08:00
就是求两个小整数数组交集，bitmap 足够快，O(m+n)
|
|
26
meteor2013 OP |
 |
27
omph 2015-07-20 10:16:40 +08:00
楼主表达能力堪忧，早该按 17 楼表达清楚
C++ 可以把 A 存到 map，key 是开始时间，val 是结束时间 使用 lower_bound，upper_bound 把 B 的开始和结束到 map 中定位（二分查找），两个定位的中间部分就是重叠部分 因 AB 有序，所以后续定位不用从头开始 |
 |
28
kzzhr 2015-07-20 10:21:04 +08:00
区间树干这个是不是太重了。。
这好像是当年学hash的经典题型，题意不是很清楚。。 |
|
29
meteor2013 OP |
 |
30
ant_sz 2015-07-20 11:14:13 +08:00
先把两个序列都处理成 [start, end] 这样range 的序列，然后用两个指针指向两个range序列的头，依次后移两个指针来计算range的交。这应该是一个 O(M+N)的算法，我觉得应该比 O(M log N) 的 要好。
1. 如果 a 指向的 range 的结束时间 大于 b 指向的range 的开始时间，把 a 往后移动，反之亦然。 2. 如果 a 指向的 range 和 b 指向的 range 有交集，求交集并加入结果，然后将 a 和 b 结束时间较早的那个往后移动。 @meteor2013 另外，二分查找的性能其实是非常好的。A 和 B 序列非常大，最大能有多大呢？2^32 = 4G 个元素算不算大？然而用二分查找只需要 32 次迭代。二分查找的问题在于如果序列非常大，可能难以全部load到内存里，而且二分查找的时候有可能访问的内存位置跳跃比较大，因此可能需要频繁的置换虚拟内存。 线段树的查询也是需要 O(log N) 的时间的，而且你总要遍历其中一个序列所以时间复杂度综合来看也差不多 O(M log N) ，而且线段树的实现比较复杂，需要的内存空间大约是 O(2N) ，而且不一定有二分查找快，建树本身需要 O(N) 的时间复杂度。所以我觉得并不是一个好的方法。 |
 |
31
ffffwh 2015-07-20 11:22:09 +08:00
从左到右linear scan，碰到开闭区间标记一下
|
 |
32
stackpop 2015-07-20 12:19:01 +08:00
准确描述问题先吧。
根据你的描述，求的是离散的点的交集啊，数据是有序的，因而就是最长公共子序列啊。 如果说是很多个时间区间的集合，然后求哪些时间段有交叉，需要使用线段树。 |
 |
33
yuankui 2015-07-20 12:36:25 +08:00
1. 两个序列排序
2. 两个指针指向两个序列 3. 谁小谁后移 4. 相等的话,就加入result_list,并且同时后移 5. 直到有一个指针到末尾 如果时间序列没有排序的话,这是个O(2*logN + N) = O(logN)的算法 如果有序的话,这是个O(N)的算法 |
|
34
messyidea 2015-07-20 13:27:24 +08:00
AB序列非常大的话可以进行一次预处理，先离散化数据。
|
 |
35
XadillaX 2015-07-20 14:53:19 +08:00
线段树正解。
|
 |
36
KotiyaSanae 2015-07-20 15:16:09 +08:00
|
|
37
KotiyaSanae 2015-07-20 15:18:04 +08:00
……按错键发出去了。这篇paper前半部分讨论了几种（三种？）方法，找交集。里面有一个双堆法，个人感觉挺有意思。
|
 |
38
qwsqwa 2015-07-20 15:36:59 +08:00
@yuankui 是正解。
楼主给的数据不是时间段，是时间点，只是几个时间点连起来就是时间段了。 如果给的是若干时间段，比如原问题中 A： 3,4,5, 7,8,910, 18,19 B: 4,5, 16,17,18,19,20 写成 A：3,5,7,10,18,19 B：4,5,16,20 的话才会用到线段树。 |
 |
39
qw7692336 2015-07-20 20:47:57 +08:00
经过排序到数据？
|
|
41
kzzhr 2015-08-03 17:57:52 +08:00
@meteor2013 所以我说hash嘛。区间数烧内存是小事，关键是需求没那么复杂，就比如现在让你找(1,n)的最大值，你也可以先排个序，问题是没有必要。奥对了，#33也给出了logn的解法，跟线段树时间一样，但是编码复杂度小很多。不过个人觉得还是hash优先。
|
Select Language