i*********7
发帖数: 348 | 1 如果给你一个arraylist，里面装的都是time span，
可以假设数据结构如下。
class TimeSpan{
Long startTime;
Long endTime;
};
ArrayList
假设这个List是按照startTime排好序的。
现在我给你一个time，能否低于O(n)的方法找到所有startTime<=time<=endTime的span？
我知道可以用O(logn)的算法知道有多少个这样的span，但有没有办法低于O(n)还能找
出全部？而不仅仅是知道个数。
===========
好吧，我可能说的也有问题，我觉得O(logn)是没办法知道的，当俺错了。TAT。。 |
e****e
发帖数: 418 | 2 interval tree. watch MIT introduction to algorithm lecture video for details
. |
w**********o
发帖数: 140 | 3 ls的算法有问题，或者说我不太理解。
如果我们自己建立tree的话，本身就要O(nlogn), 反而比直接扫list里面span更费时间。
回答lz问题， 我感觉应该没有了。 因为，如果题目问的是找到所有符合条件的， 至
少是n。
希望lz重新说下问题是什么， 谢谢。 |
g*c
发帖数: 4510 | 4 同意。
间。
【在 w**********o 的大作中提到】
: ls的算法有问题，或者说我不太理解。
: 如果我们自己建立tree的话，本身就要O(nlogn), 反而比直接扫list里面span更费时间。
: 回答lz问题， 我感觉应该没有了。 因为，如果题目问的是找到所有符合条件的， 至
: 少是n。
: 希望lz重新说下问题是什么， 谢谢。
|
H****s
发帖数: 247 | 5 楼主的问题是找全部，这个用interval tree没帮助吧！
details
【在 e****e 的大作中提到】
: interval tree. watch MIT introduction to algorithm lecture video for details
: .
|
y****n
发帖数: 743 | 6 以当前的List结构，不可能O(logn)，因为TimeSpan之间可能重叠。
但是，如果那个FindTimeSpan()会被调用很多次。
我们可以考虑重新构造数据结构，转换成有序不重叠的TimeSpan List。
这样，以空间换时间，就可以O(logn)查找了。
span？
【在 i*********7 的大作中提到】
: 如果给你一个arraylist，里面装的都是time span，
: 可以假设数据结构如下。
: class TimeSpan{
: Long startTime;
: Long endTime;
: };
: ArrayList
: 假设这个List是按照startTime排好序的。
: 现在我给你一个time，能否低于O(n)的方法找到所有startTime<=time<=endTime的span？
: 我知道可以用O(logn)的算法知道有多少个这样的span，但有没有办法低于O(n)还能找
|
p*****2
发帖数: 21240 | 7
题目要求找出全部
【在 y****n 的大作中提到】
: 以当前的List结构，不可能O(logn)，因为TimeSpan之间可能重叠。
: 但是，如果那个FindTimeSpan()会被调用很多次。
: 我们可以考虑重新构造数据结构，转换成有序不重叠的TimeSpan List。
: 这样，以空间换时间，就可以O(logn)查找了。
:
: span？
|
y****n
发帖数: 743 | 8 详细说几句：
就题目本身而言，FindTimeSpan()一次调用，那一定是O(n)。
但实际项目中，如果FindTimeSpan()被多次（比如：百万次）调用，并且非常需要迅速
返回结果（比如：某个在线服务）。那么我们可以重新构造数据结构有利于查询，以空
间换时间。
思路一：根据时长分类：
原题：假设这个List是按照startTime排好序的。
如果我们再假设，每个TimeSpan的时常都是1分钟，那么这道题是不是可以O(logn)?
好像可以了吧？
请注意，我所说的O(logn)是指以O(logn)的速度跳过不想要的结果。
如果我们再假设，每个TimeSpan的时常都是1-2分钟，我们是不是还可以O(logn)?
好像平均情况可以O(logn)，最坏情况还是O(n)
那么如果我们把所有的TimeSpan分成4个list：
[0-1分钟]，[1分钟-1小时]，[1小时-1天]，[1天-最大]
对于每个分段分别查询，这样是不是可以做到平均情况O(logn)?
前面的分段只是假设，如果能分析所有TimeSpan时长的出现概率，会得到更合理的分割
边界。那么平均速度会非常接近O(logn)
思路二：构建不重叠TimeSpanRef
建立新的class。
class TimeSpanRef{
Long startTime;
List references;
};
List timeSpanRefList;
每个TimeSpanRef保存着一个startTime，与下一个startTime会形成一个时间段。
references保存着所有包含此时间段的TimeSpan。
也就是说，如果找到了TimeSpanRef，也就找到了全部符合条件的TimeSpan。
我们根据List来构建List，并保持startTime的排序，那么就
可以O(logn)了。
这两种方法都可以快速有效的跳过不想要的TimeSpan。
思路三：合并前面两个思路。
分析原始List找到合理的分割边界，
再根据分割边界构建几个不重叠的List。
选择前面的哪个思路，要看具体项目。
【在 p*****2 的大作中提到】
:
: 题目要求找出全部
|
c********t
发帖数: 5706 | 9 赞
【在 y****n 的大作中提到】
: 详细说几句：
: 就题目本身而言，FindTimeSpan()一次调用，那一定是O(n)。
: 但实际项目中，如果FindTimeSpan()被多次（比如：百万次）调用，并且非常需要迅速
: 返回结果（比如：某个在线服务）。那么我们可以重新构造数据结构有利于查询，以空
: 间换时间。
: 思路一：根据时长分类：
: 原题：假设这个List是按照startTime排好序的。
: 如果我们再假设，每个TimeSpan的时常都是1分钟，那么这道题是不是可以O(logn)?
: 好像可以了吧？
: 请注意，我所说的O(logn)是指以O(logn)的速度跳过不想要的结果。
|
H****s
发帖数: 247 | 10 这个分析够牛！得顶一下！
【在 y****n 的大作中提到】
: 详细说几句：
: 就题目本身而言，FindTimeSpan()一次调用，那一定是O(n)。
: 但实际项目中，如果FindTimeSpan()被多次（比如：百万次）调用，并且非常需要迅速
: 返回结果（比如：某个在线服务）。那么我们可以重新构造数据结构有利于查询，以空
: 间换时间。
: 思路一：根据时长分类：
: 原题：假设这个List是按照startTime排好序的。
: 如果我们再假设，每个TimeSpan的时常都是1分钟，那么这道题是不是可以O(logn)?
: 好像可以了吧？
: 请注意，我所说的O(logn)是指以O(logn)的速度跳过不想要的结果。
|
