mmd,新版current 真难看，已经删除了， - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PDA - 掌中宝

mmd,新版current 真难看，已经删除了，

mmd,新版current 真难看，已经删除了，# PDA - 掌中宝

k*t2012-12-13 08:12

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

d*e2012-12-13 08:12

2 楼

真是快剥皮了，denial 也好 approval 也好给个结果就这么苦等太折磨人了

o*12012-12-13 08:12

3 楼

k*f2012-12-13 08:12

4 楼

有谁推荐个好用的，主要看cnbeta,slickdeals。

p*22012-12-13 08:12

5 楼

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里

c*o2012-12-13 08:12

6 楼

pat pat, 根据dolstats,现在处理到8月9号了，马上就有信儿啦，坚持住！

B*r2012-12-13 08:12

7 楼

k*t2012-12-13 08:12

8 楼

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里

R*d2012-12-13 08:12

9 楼

bless

【在 d*******e 的大作中提到】

: 真是快剥皮了，denial 也好 approval 也好给个结果就这么苦等太折磨人了

b*n2012-12-13 08:12

10 楼

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*22012-12-13 08:12

11 楼

当然是要有条件的。就是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*t2012-12-13 08:12

12 楼

以前看见一个版上大拿做的一个O(N)的find/union。不过那个是找
最长连续子序列，所以并集时只需更新边界元素，且并集操作只会
在边界发生。动态更新最长序列，只需扫描一遍即可。
下面是原贴。不知可否借鉴得上？
发信人: battlesc (zerg), 信区: JobHunting
标题: Re: G题讨论
发信站: BBS 未名空间站 (Fri Jul 15 11:37:33 2011, 美东)
#include
#include
using namespace std;
int main() {
//int a[8] = {101,2,3,104,5,103,9,102};
int a[9] = {100,3,200,1,2,4,3,6,7};
// Assume at least one number
int L = sizeof(a)/sizeof(a[0]);
cout << "total: " << L << endl;
map ht;
int max = 1;
int start = a[0], end = a[0];
// Scan and store number of consecutive numbers
for (int i = 0; i < L; ++i)
{
if (ht.find(a[i]) != ht.end())
continue;

int c1 = 0;
if (ht.find(a[i]+1) != ht.end())
c1 = ht[a[i]+1];
int c2 = 0;
if (ht.find(a[i]-1) != ht.end())
c2 = ht[a[i]-1];
// Update start and end in the map for the group a[i] belongs to
int newCount = c1 + c2 + 1;
ht[a[i]] = newCount;
ht[a[i]+c1] = newCount;
ht[a[i]-c2] = newCount;

// Record max
if (newCount > max)
{
max = newCount;
start = a[i] - c2;
end = a[i] + c1;
}
}
cout << start << "..." << end <return 0;
}

-