k***t
发帖数: 276 | 1 Divide a list of numbers into group of consecutive numbers but their
original order should be preserved? e.g.
8,2,4,7,1,0,3,6
2,4,1,0,3 and 8,7,6
obviously in shortest time and space.
=========================================
看到一个comment，但不确定其中的find/union是否可以O(n)实现。
1. Identify range - One pass
2. Identify number of elements within each range - One pass
3. Fill destination array by maintaining starting positions of each range -
One pass of source array.
O(n) time and O(n) space | p*****2
发帖数: 21240 | 2 8,2,4,7,1,0,3,6
第一遍得到最小值0， 最大值8
bool[] flags=new bool[9];
第二遍填flags, {1,1,1,1,1,0,1,1,1}
第三遍得到两个group 0-4 6-8
开两个list
第四遍，把每个数填到相应的list里 | k***t
发帖数: 276 | 3 1. What if a[4]=100000? Not O(n) space any more, but O(Max) space.
2. In step 4, for given i=0..n-1, how do we know which list/group a[i]
belongs to?
【在 p*****2 的大作中提到】
: 8,2,4,7,1,0,3,6
: 第一遍得到最小值0， 最大值8
: bool[] flags=new bool[9];
: 第二遍填flags, {1,1,1,1,1,0,1,1,1}
: 第三遍得到两个group 0-4 6-8
: 开两个list
: 第四遍，把每个数填到相应的list里
| b*****n
发帖数: 482 | 4 my 2 cents:
It seems O(n) is not possible, should be at least O(nlgn). Worst case
scenario, all the numbers belong to their own group, meaning no two numbers
are consecutive. Then each number has to be compared with existing group to
find out whether it belongs to them or has to be in a new group of his own.
Anything based on comparison like this has a low bound of O(nlgn). Of course
, if the storage can be O(Max), then O(n) time can be realized, similar to
the counting algorithm. | p*****2
发帖数: 21240 | 5 当然是要有条件的。就是number的范围有限。
in step 4, 可以用binary search, 如果group数目小的话，可以忽略。如果想得纯O(n
),可以用hashtable.
【在 k***t 的大作中提到】
: 1. What if a[4]=100000? Not O(n) space any more, but O(Max) space.
: 2. In step 4, for given i=0..n-1, how do we know which list/group a[i]
: belongs to?
| k***t
发帖数: 276 | 6 以前看见一个版上大拿做的一个O(N)的find/union。不过那个是找
最长连续子序列，所以并集时只需更新边界元素，且并集操作只会
在边界发生。动态更新最长序列，只需扫描一遍即可。
下面是原贴。不知可否借鉴得上？
发信人: battlesc (zerg), 信区: JobHunting
标 题: Re: G题讨论
发信站: BBS 未名空间站 (Fri Jul 15 11:37:33 2011, 美东)
#include
#include |
|
