l**********9
发帖数: 537 | 1 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
。。。有start integer number，end interger number2个fields，按照先start
number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素 | d*k
发帖数: 207 | 2 It can be solved by the 'classic' method.
There are three kinds of point:
1. The start points of an interval
2. The end points of an interval
3. The points in second array.
Put them into one array and sort it by increasing position. One detail: for
points with same position, use the order: type1 < type3 < type2
Iterate the sorted array and maintain on status: number of opening intervals
so far. Let's denote it as N.
Initially, N = 0.
For each point, if it's type1, let N = N + 1. If it's type2, Let N = N - 1.
If it's type3, that point is 'out of range' iff N is zero.
P.S.
In a Linux box and the CN input method is broken yet again.... | e*******8
发帖数: 94 | 3 这个就是plane sweep的方法。因为输入已经排好序了，所以时间复杂度是O（n），n是
第一个数列的大小＋第二个数列的大小
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
| l**********9
发帖数: 537 | 4 谢谢回复， 将它们merge到一个array时，是不是还需要记录它们的type？比如 2start
, 4end, 5, 6start, 9end ...? 因为iterate merged的数组的时候还需要判断是哪种
类型的。
不知道leetcode上面有没有类似的题目？
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
| z****e
发帖数: 54598 | | d*k
发帖数: 207 | 6 当然要记录类型。。。不是说了吗，排序的时候也得看类型。
leetcode好像有吧，记不清了。
2start
【在 l**********9 的大作中提到】
: 谢谢回复， 将它们merge到一个array时，是不是还需要记录它们的type？比如 2start
: , 4end, 5, 6start, 9end ...? 因为iterate merged的数组的时候还需要判断是哪种
: 类型的。
: 不知道leetcode上面有没有类似的题目？
:
: for
: intervals
| R***Z
发帖数: 1167 | 7 想确认一下我对题的理解是否有误，这题中数组1是以下哪种形式？
A: {[start1, end1], [start2, end2]， ...}
B: {start1, start2, ..., end1, end2， ...}
-9
integer
【在 l**********9 的大作中提到】
: 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
: 。。。有start integer number，end interger number2个fields，按照先start
: number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
: 。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
| s****p
发帖数: 124 | 8 When you merge and sort, that can take O(nlogn), right? It is not linear
time algorithm.
for
intervals
【在 d*k 的大作中提到】
: It can be solved by the 'classic' method.
: There are three kinds of point:
: 1. The start points of an interval
: 2. The end points of an interval
: 3. The points in second array.
: Put them into one array and sort it by increasing position. One detail: for
: points with same position, use the order: type1 < type3 < type2
: Iterate the sorted array and maintain on status: number of opening intervals
: so far. Let's denote it as N.
: Initially, N = 0.
| e*******8
发帖数: 94 | 9 不用直接排序啊（因为题目是说已经排好序之后怎么做）。不知道这步按照结束时间排
序是做什么，觉得好象没必要？要是可以单按照start time一个一个处理每个range，
我觉得算法
就是leetcode上的jump game ＋ merge sort中merge两个排好序的数组。
【在 s****p 的大作中提到】
: When you merge and sort, that can take O(nlogn), right? It is not linear
: time algorithm.
:
: for
: intervals
| s*w
发帖数: 729 | 10 用 hashtable 应该是最好理解的了
for interval in array 1:
for value in interval:
hashtable.insert(value)
for int in array 2:
if hashtable.count(int)==0:
output
唯一的缺点是第二行可能比较慢，看共有多少 unique value
-9
integer
【在 l**********9 的大作中提到】
: 有人做过这个题没有: 2个排序数组，数组1的元素是integer range， 例如 2-4， 5-9
: 。。。有start integer number，end interger number2个fields，按照先start
: number排序，再end number排序，每个元素就是一个range。 第二个数组是integer
: 。 2个都是升序。 问找出第二个数组里面不在第一个数组所有range的所有元素
| | | s****p
发帖数: 124 | 11 Array 1 is sorted by range, if r1 < r2, it could be that r1.upper > r2.lower
. So when you merge lower and upper into the same array, it still need to be
sorted.
【在 e*******8 的大作中提到】
: 不用直接排序啊（因为题目是说已经排好序之后怎么做）。不知道这步按照结束时间排
: 序是做什么，觉得好象没必要？要是可以单按照start time一个一个处理每个range，
: 我觉得算法
: 就是leetcode上的jump game ＋ merge sort中merge两个排好序的数组。
| p*****2
发帖数: 21240 | 12 如果把第一个merge的话是O(n), 然后找的话就是O(logn)了吧？ | e*******8
发帖数: 94 | 13 所以我才觉得不用按照finish time排序呀：要是单按照start time排序， events就只
是第一个array里的start time和第二个array里的点：依此扫描每个events （用merge
sort里merge两个sorted array的方法）：如果是start time，就检查是否可以向右扩
展被intervals覆盖的范围，然后相应的更新最大可以覆盖的范围；如果是第二个array
里的点，就检查是不是在当前被覆盖的范围内。
比如如果输入是［１，４］， ［２，５］， ［７，９］，［８，１０］，第二个
array的点是５，６，那么：
第一个event at １：当前覆盖的范围是［１，４］
第二个event at ２：当前覆盖的范围是［１，５］
第三个event at ５：５被覆盖
第四个event at ６：６没有被覆盖；
第五个event at ７：当前覆盖的范围是［７，９］
第六个event at ８：当前覆盖的范围是 ［７，１０］
最后输出是{6}。 | r*********n
发帖数: 4553 | 14 这种题目一看就知道对方想考察的是binary search的变体
描述算法比较verbose，这里给个例子
interval array A: [{1, 3}, {3, 4}, {7, 12}, {9, 10}] //按照[1, 3, 7, 9]来排
的顺
integer array B: [4, 5, 10]
1. binary search (actually upper_bound) B[0] = 4 in A: get i = 2 （if A[i]==
4，then ++i）
2. iterate through A[0, ..., i-1] until you find the first index j such that
its end time is >= 4: j = 1
3. because j < i, 4 is contained in an interval
4. binary search B[1] = 5 in A: get i = 2
5. iterate through A[j, ..., i-1] (j = 1) until you find the first index
such that its end time is >= 5: j = 2
6. because j == i, 5 is not contained in an interval
7. binary search B[2] = 10 in A: get i = 4
8. iterate through A[j, ..., i-1] (here j = 2)...... end time is >= 10: j =
2
9. because j < i, 10 is contained in A
because j is non-decreasing, iteration step (above 2, 5, 8) takes O(n), each
binary search takes O(logn), total running time is O(nlogn) | c********p
发帖数: 1969 | |
|
