由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - G题讨论
相关主题
● Random Array number, Find longest consecutive sequence● Question:Given a array,find out if there exist a subarray such its sum is zero
● 砸了面试，发面题● 问个anagram的问题
● C++问题3● Unique Binary Search Trees的变形
● leetcode-- scramble string● leetcode N-Queens II 我的c++要400多毫秒
● 好挫的F家面经● topcoder- strange country problem.
● 大牛来做一下这道题● 给定字符串，求其不出现重复字符的子字符串的最大长度
● 请教一道题● 问个MSFT的题
● Divide num list into grp of consecutive nums with order preserved● 大家帮我看看这个程序哪里有问题啊！！
相关话题的讨论汇总
话题: int话题: newcount话题: ht话题: map话题: max
进入JobHunting版参与讨论
1 (共1页)
r******n
发帖数: 170
1
从careercup上看的，
Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104
Can we do it in one go on array using extra space??
觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
的连续数组。
g*****k
发帖数: 623
2
如果要求O(n)的算法，那么我能想到的也就是用bit vector再扫描一次了。
这里的using extra space是指没有限制吗？

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
b**********r
发帖数: 91
3
Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
p****y
发帖数: 67
4
It is right. And for each set, only keep the min number and max number of
the set.
g*****i
发帖数: 2162
5
如果浏览disjoint set算法弄出来来的set? 是不是还要扫一遍所有的数,判断是不是在
这个set里 (forester的实现方法)?

【在 b**********r 的大作中提到】
: Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.
a********m
发帖数: 15480
6
添加到disjoint set需要多少时间？

【在 b**********r 的大作中提到】
: Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.
s*******e
发帖数: 4188
7
楼上的optimization不错，只要记min and max for the consecutive numbers set.

【在 a********m 的大作中提到】
: 添加到disjoint set需要多少时间？
g**********y
发帖数: 14569
8
如果数都不连续，这个解法是O(n^2), 即使把Hashtable排序，也是O(nlogn)。如果O(
nlogn), 可能直接排序，然后数更直接。
O(n)的算法，有吗？
我看careercup上的讨论，没人给出O(n)的。

【在 b**********r 的大作中提到】
: Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.
a********m
发帖数: 15480
9
可是还不是o(n).
一个朋友用双hash做到了o(n).

【在 s*******e 的大作中提到】
: 楼上的optimization不错，只要记min and max for the consecutive numbers set.
d*******l
发帖数: 338
10
用路径压缩的并查集的话，每次操作的代价几乎是常数，一遍扫描就能出结果，可以认
为是O(n)的。题目说让一遍扫描出结果，否则用hash的话两遍扫描也可以出结果，也是
O(n)的。

【在 g**********y 的大作中提到】
: 如果数都不连续，这个解法是O(n^2), 即使把Hashtable排序，也是O(nlogn)。如果O(
: nlogn), 可能直接排序，然后数更直接。
: O(n)的算法，有吗？
: 我看careercup上的讨论，没人给出O(n)的。
相关主题
● 大牛来做一下这道题● Question:Given a array,find out if there exist a subarray such its sum is zero
● 请教一道题● 问个anagram的问题
● Divide num list into grp of consecutive nums with order preserved● Unique Binary Search Trees的变形
进入JobHunting版参与讨论
a********m
发帖数: 15480
11
感觉不对。 压缩的话每次查找接触的块是lgm(m是块数，算是n的函数，理论上不是常
数)

【在 d*******l 的大作中提到】
: 用路径压缩的并查集的话，每次操作的代价几乎是常数，一遍扫描就能出结果，可以认
: 为是O(n)的。题目说让一遍扫描出结果，否则用hash的话两遍扫描也可以出结果，也是
: O(n)的。
d*******l
发帖数: 338
12
这个在上面给的链接和算法导论上都有相关的分析，确实是n的函数，但增长非常慢，
对于我们可以想得到的n，几乎不会超过5。实际运行中效果也确实如此。关键题目说一
次扫描就要出来，那这样做比较方便，否则扫两次就能很直接的做到O(n)。

【在 a********m 的大作中提到】
: 感觉不对。 压缩的话每次查找接触的块是lgm(m是块数，算是n的函数，理论上不是常
: 数)
a********m
发帖数: 15480
13
扫两次怎么做？

【在 d*******l 的大作中提到】
: 这个在上面给的链接和算法导论上都有相关的分析，确实是n的函数，但增长非常慢，
: 对于我们可以想得到的n，几乎不会超过5。实际运行中效果也确实如此。关键题目说一
: 次扫描就要出来，那这样做比较方便，否则扫两次就能很直接的做到O(n)。
P**********c
发帖数: 3417
14
建一个包括所有数range的array, 对每个数标记是否存在，然后扫一遍这个大array?
不过这个就是O(range), 不是O(n)

【在 a********m 的大作中提到】
: 扫两次怎么做？
a********m
发帖数: 15480
15
这个肯定太基本。关键就是怎么不扫描[min,max]的所有数.

【在 P**********c 的大作中提到】
: 建一个包括所有数range的array, 对每个数标记是否存在，然后扫一遍这个大array?
: 不过这个就是O(range), 不是O(n)
d*******l
发帖数: 338
16
只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
#include
#include
using namespace std;
int count(int a, map &m)
{
if(m[a] > 1)
return m[a];
else if(!m[a+1])
return 1;
m[a] = 1 + count(a+1, m);
return m[a];
}
void solve(int a[], int n)
{
map m;
int i;
for(i = 0; i < n; i++)
m[a[i]] = 1;
int mx = 0, p;
for(i = 0; i < n; i++) {
int t = count(a[i], m);
if(t > mx) {
mx = t;
p = a[i];
}
}
for(i = 0; i < mx; i++)
cout << p + i << " ";
cout << endl;
}

【在 a********m 的大作中提到】
: 这个肯定太基本。关键就是怎么不扫描[min,max]的所有数.
P**********c
发帖数: 3417
17
map不是hashmap啊。map的插入和查找都是O(lgn). 就算插入查找都是O(1)，你这个也不是O(n), 这个要看map access
不存在的key的behavior。这种情况下它会插入一个新的key的，插入一个key么至少就是O(1)。所以你在不停的判断
m[a+1]的时候，map的size最终会涨到这组数的range, 同时时间复杂度也涨到O(range)了. hash_map有同样的问题。
hash_map也是从最底层实现起来的，它不是一个magical的只存n个数就可以O(n) access m(m>>n)个值的工具。

【在 d*******l 的大作中提到】
: 只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
: #include
: #include
: using namespace std;
: int count(int a, map &m)
: {
: if(m[a] > 1)
: return m[a];
: else if(!m[a+1])
: return 1;
b******c
发帖数: 70
18
#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;
}

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
r******n
发帖数: 170
19
这里有解答：
http://dzmitryhuba.blogspot.com/2011/02/longest-consecutive-ele

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
d*******l
发帖数: 338
20
C++里不是没有标准的hash_map实现吗，想成hashmap就行。
至于你后面的分析我就看不懂了，如果你说的是数据结构的问题，那存n个元素的
hashmap可以做到O(n)空间，插入删除查找都是O(1)（期望，平摊），这点我挺确定的
。所以不妨把每一次访问map都看作是访问数组，就是O(1)。这样的话平均每个元素访
问map的次数不超过3次，就是O(n)的啊

也不是O(n), 这个要看map access
就是O(1)。所以你在不停的判断
range)了. hash_map有同样的问题。
access m(m>>n)个值的工具。

【在 P**********c 的大作中提到】
: map不是hashmap啊。map的插入和查找都是O(lgn). 就算插入查找都是O(1)，你这个也不是O(n), 这个要看map access
: 不存在的key的behavior。这种情况下它会插入一个新的key的，插入一个key么至少就是O(1)。所以你在不停的判断
: m[a+1]的时候，map的size最终会涨到这组数的range, 同时时间复杂度也涨到O(range)了. hash_map有同样的问题。
: hash_map也是从最底层实现起来的，它不是一个magical的只存n个数就可以O(n) access m(m>>n)个值的工具。
相关主题
● leetcode N-Queens II 我的c++要400多毫秒● 问个MSFT的题
● topcoder- strange country problem.● 大家帮我看看这个程序哪里有问题啊！！
● 给定字符串，求其不出现重复字符的子字符串的最大长度● F家伪面经，求bless
进入JobHunting版参与讨论
d*******l
发帖数: 338
21
这个不错，扫一遍就出来了，很严谨的O(n)。

【在 b******c 的大作中提到】
: #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;
a********m
发帖数: 15480
22
这个不对。
ht[a[i]] = newCount;
ht[a[i]+c1] = newCount;
ht[a[i]-c2] = newCount;

【在 b******c 的大作中提到】
: #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;
d*******l
发帖数: 338
23
刚才想了几个例子，到没发现有什么问题。哪种情况会有问题？

【在 a********m 的大作中提到】
: 这个不对。
: ht[a[i]] = newCount;
: ht[a[i]+c1] = newCount;
: ht[a[i]-c2] = newCount;
a********m
发帖数: 15480
24
试了一下，似乎是可以。永远保存边界是对的。可是还是有点不放心，还需要再想想。

【在 d*******l 的大作中提到】
: 刚才想了几个例子，到没发现有什么问题。哪种情况会有问题？
d*******l
发帖数: 338
25
我觉得逻辑上是对的，只要别有重复插入就行。这一点代码里有体现。

【在 a********m 的大作中提到】
: 试了一下，似乎是可以。永远保存边界是对的。可是还是有点不放心，还需要再想想。
a********m
发帖数: 15480
26
重复插入不怕，反正能查出来。

【在 d*******l 的大作中提到】
: 我觉得逻辑上是对的，只要别有重复插入就行。这一点代码里有体现。
b******c
发帖数: 70
27
I want to make the code shorter so removed the check

【在 a********m 的大作中提到】
: 试了一下，似乎是可以。永远保存边界是对的。可是还是有点不放心，还需要再想想。
d*******l
发帖数: 338
28
我觉得你的是对的，因为如果排除了重复插入的话，新插入的元素左右两边肯定是某个
group的边界，所以只考虑边界应该是安全的。甚至你代码中h[a[i]] = newCount都是
不必要的。
我的想法是第一遍先把所有数都放进map，第二遍扫描的时候求当前的数向右连续多长
，并更新所有经过的数对应的值。每个数对应的值最多只求一遍，所以每个数访问map
的次数平均就2－3次，应该也是O(n)的。

【在 b******c 的大作中提到】
: I want to make the code shorter so removed the check
g*****k
发帖数: 623
29
似乎不对，
举个例子吧，假设有2个区段，[m..i], [i+2..j]
并且下一步处理 i+1和j-1
处理i+1将使得ht[m]=ht[j]=j-m+1
但是处理j-1的时候，假设ht[j-2]=t(some old value)
之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
束。

#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;
}

【在 b******c 的大作中提到】
: #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;
d*******l
发帖数: 338
30
这个就是重复插入的问题，因为如果已经有区间[i+2, j]，那j-1肯定已经插入过了。
他的代码中对于已经存在于map中的元素直接continue了。

【在 g*****k 的大作中提到】
: 似乎不对，
: 举个例子吧，假设有2个区段，[m..i], [i+2..j]
: 并且下一步处理 i+1和j-1
: 处理i+1将使得ht[m]=ht[j]=j-m+1
: 但是处理j-1的时候，假设ht[j-2]=t(some old value)
: 之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
: 束。
:
: #include
: #include
相关主题
● (已解决，code错了) online judge 有的时候会有点小bug吗？● 砸了面试，发面题
● 一道复杂的题，求解法● C++问题3
● Random Array number, Find longest consecutive sequence● leetcode-- scramble string
进入JobHunting版参与讨论
a********m
发帖数: 15480
31
假设新的数不在hash里面。左面的如果有值就肯定是结束。右面是开始。

【在 g*****k 的大作中提到】
: 似乎不对，
: 举个例子吧，假设有2个区段，[m..i], [i+2..j]
: 并且下一步处理 i+1和j-1
: 处理i+1将使得ht[m]=ht[j]=j-m+1
: 但是处理j-1的时候，假设ht[j-2]=t(some old value)
: 之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
: 束。
:
: #include
: #include
g*****k
发帖数: 623
32
收到

【在 d*******l 的大作中提到】
: 这个就是重复插入的问题，因为如果已经有区间[i+2, j]，那j-1肯定已经插入过了。
: 他的代码中对于已经存在于map中的元素直接continue了。
g*****k
发帖数: 623
33
呵呵，是地

【在 a********m 的大作中提到】
: 假设新的数不在hash里面。左面的如果有值就肯定是结束。右面是开始。
j*****p
发帖数: 108
34

Map不是hashtable吧？ 所以find不是O(1)操作

【在 d*******l 的大作中提到】
: 这个不错，扫一遍就出来了，很严谨的O(n)。
g**********y
发帖数: 14569
35
赞！关键点找得很好。

【在 b******c 的大作中提到】
: #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;
d*******l
发帖数: 338
36
额，前面说了C++标准库没有hashmap的实现所以就用map了，想成hashmap就行了。方法
都是一样的。

【在 j*****p 的大作中提到】
:
: Map不是hashtable吧？ 所以find不是O(1)操作
k****n
发帖数: 369
37
union-find set.
For each input x, first set p[x] = x; then union x with x-1 and x+1 if
available
During union update, keep set size and update max size.
In one go and the time complexity is O(n*alpha(n)) ~~ O(n)

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
k****n
发帖数: 369
38

int *p;
int *sz;
void init() {
p = (int *) malloc(sizeof(int)*(MAX_INT));
sz = (int *) malloc(sizeof(int)*(MAX_INT));
memset(p, 0, sizeof(int)*MAX_INT);
memset(sz, 0, sizeof(int)*MAX_INT);
}
void clean() {
free(p); free(sz);
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
int union(int x, int y) {
int rx = find(x);
int ry = find(y);
if (rx == ry) {
return sz[rx];
} else if (sz[rx] > sz[ry]) {
p[ry] = rx;
sz[rx] += sz[ry];
return sz[rx];
} else {
p[rx] = ry;
sz[ry] += sz[rx];
return sz[ry];
}
}
int eat(int x) {
if (p[x] != 0) return;
p[x] = x; sz[x] = 1;
union(x, x-1);
return union(x, x+1);
}
int scan(int a[], int n) {
init();
int i;
int max = 0;
for (i=0; i int m = eat(a[i]);
if (m > max) max = m;
}
clean();
return max;
}

【在 k****n 的大作中提到】
: union-find set.
: For each input x, first set p[x] = x; then union x with x-1 and x+1 if
: available
: During union update, keep set size and update max size.
: In one go and the time complexity is O(n*alpha(n)) ~~ O(n)
P**********c
发帖数: 3417
39
嗯，我看得不太仔细，你的解法应该是对的。

【在 d*******l 的大作中提到】
: C++里不是没有标准的hash_map实现吗，想成hashmap就行。
: 至于你后面的分析我就看不懂了，如果你说的是数据结构的问题，那存n个元素的
: hashmap可以做到O(n)空间，插入删除查找都是O(1)（期望，平摊），这点我挺确定的
: 。所以不妨把每一次访问map都看作是访问数组，就是O(1)。这样的话平均每个元素访
: 问map的次数不超过3次，就是O(n)的啊
:
: 也不是O(n), 这个要看map access
: 就是O(1)。所以你在不停的判断
: range)了. hash_map有同样的问题。
: access m(m>>n)个值的工具。
I******k
发帖数: 378
40
是nlogn吧

【在 d*******l 的大作中提到】
: 这个不错，扫一遍就出来了，很严谨的O(n)。
相关主题
● leetcode-- scramble string● 请教一道题
● 好挫的F家面经● Divide num list into grp of consecutive nums with order preserved
● 大牛来做一下这道题● Question:Given a array,find out if there exist a subarray such its sum is zero
进入JobHunting版参与讨论
h***i
发帖数: 1970
41
tr1::unordered_map

【在 d*******l 的大作中提到】
: C++里不是没有标准的hash_map实现吗，想成hashmap就行。
: 至于你后面的分析我就看不懂了，如果你说的是数据结构的问题，那存n个元素的
: hashmap可以做到O(n)空间，插入删除查找都是O(1)（期望，平摊），这点我挺确定的
: 。所以不妨把每一次访问map都看作是访问数组，就是O(1)。这样的话平均每个元素访
: 问map的次数不超过3次，就是O(n)的啊
:
: 也不是O(n), 这个要看map access
: 就是O(1)。所以你在不停的判断
: range)了. hash_map有同样的问题。
: access m(m>>n)个值的工具。
m**q
发帖数: 189
42
mark

【在 b******c 的大作中提到】
: #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;
c*********t
发帖数: 2921
43
Hi getback,
你说的 bit vector是不是就是C++ STL里的bitset?
你用bit vector,解决这个题，要用到多大的extra space? 我的理解是我们不知道数的
范围，所以如果最大的数有可能是2^31-1,是不是这个bit vector也用可能要有这么大
？这样的话，占用的空间太大了。感觉扫描这个bit vector的时间也不是O(n),而是等
于最大的数。
谢谢！

【在 g*****k 的大作中提到】
: 如果要求O(n)的算法，那么我能想到的也就是用bit vector再扫描一次了。
: 这里的using extra space是指没有限制吗？
h**********8
发帖数: 267
44
mark

【在 b******c 的大作中提到】
: #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;
g*****k
发帖数: 623
45
是的，你说的是对的，大家已经讨论过了。你看看大家的讨论。

【在 c*********t 的大作中提到】
: Hi getback,
: 你说的 bit vector是不是就是C++ STL里的bitset?
: 你用bit vector,解决这个题，要用到多大的extra space? 我的理解是我们不知道数的
: 范围，所以如果最大的数有可能是2^31-1,是不是这个bit vector也用可能要有这么大
: ？这样的话，占用的空间太大了。感觉扫描这个bit vector的时间也不是O(n),而是等
: 于最大的数。
: 谢谢！
s******n
发帖数: 226
46
在java里， 我把a[i]当key， 一个node当value， node里存prev和next，true/false
表示有还是没有，这样就成了一个链表，每扫一个数，向前走到头，向后走到头，记录
长度，顺便在map里删掉，这样就O（n）了。
多多指教
h******n
发帖数: 68
47
赞，学习了，mark

【在 b******c 的大作中提到】
: #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;
r******n
发帖数: 170
48
从careercup上看的，
Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104
Can we do it in one go on array using extra space??
觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
的连续数组。
g*****k
发帖数: 623
49
如果要求O(n)的算法，那么我能想到的也就是用bit vector再扫描一次了。
这里的using extra space是指没有限制吗？

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
b**********r
发帖数: 91
50
Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
相关主题
● 问个anagram的问题● topcoder- strange country problem.
● Unique Binary Search Trees的变形● 给定字符串，求其不出现重复字符的子字符串的最大长度
● leetcode N-Queens II 我的c++要400多毫秒● 问个MSFT的题
进入JobHunting版参与讨论
p****y
发帖数: 67
51
It is right. And for each set, only keep the min number and max number of
the set.
g*****i
发帖数: 2162
52
如果浏览disjoint set算法弄出来来的set? 是不是还要扫一遍所有的数,判断是不是在
这个set里 (forester的实现方法)?

【在 b**********r 的大作中提到】
: Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.
a********m
发帖数: 15480
53
添加到disjoint set需要多少时间？

【在 b**********r 的大作中提到】
: Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.
s*******e
发帖数: 4188
54
楼上的optimization不错，只要记min and max for the consecutive numbers set.

【在 a********m 的大作中提到】
: 添加到disjoint set需要多少时间？
g**********y
发帖数: 14569
55
如果数都不连续，这个解法是O(n^2), 即使把Hashtable排序，也是O(nlogn)。如果O(
nlogn), 可能直接排序，然后数更直接。
O(n)的算法，有吗？
我看careercup上的讨论，没人给出O(n)的。

【在 b**********r 的大作中提到】
: Use Disjoint set data structure http://en.wikipedia.org/wiki/Disjoint-set_data_structure and a hash table, the hash key is the value in the array, the value is a disjoint set containing the key, if (x-1) or (x+1) is in the table, then join the sets, otherwise make a set containing the key itself. Keep a sentinel of the set with the max number of values. at the end of the scan, the sentinel points to the set with the longest consecutive sequence.
a********m
发帖数: 15480
56
可是还不是o(n).
一个朋友用双hash做到了o(n).

【在 s*******e 的大作中提到】
: 楼上的optimization不错，只要记min and max for the consecutive numbers set.
d*******l
发帖数: 338
57
用路径压缩的并查集的话，每次操作的代价几乎是常数，一遍扫描就能出结果，可以认
为是O(n)的。题目说让一遍扫描出结果，否则用hash的话两遍扫描也可以出结果，也是
O(n)的。

【在 g**********y 的大作中提到】
: 如果数都不连续，这个解法是O(n^2), 即使把Hashtable排序，也是O(nlogn)。如果O(
: nlogn), 可能直接排序，然后数更直接。
: O(n)的算法，有吗？
: 我看careercup上的讨论，没人给出O(n)的。
a********m
发帖数: 15480
58
感觉不对。 压缩的话每次查找接触的块是lgm(m是块数，算是n的函数，理论上不是常
数)

【在 d*******l 的大作中提到】
: 用路径压缩的并查集的话，每次操作的代价几乎是常数，一遍扫描就能出结果，可以认
: 为是O(n)的。题目说让一遍扫描出结果，否则用hash的话两遍扫描也可以出结果，也是
: O(n)的。
d*******l
发帖数: 338
59
这个在上面给的链接和算法导论上都有相关的分析，确实是n的函数，但增长非常慢，
对于我们可以想得到的n，几乎不会超过5。实际运行中效果也确实如此。关键题目说一
次扫描就要出来，那这样做比较方便，否则扫两次就能很直接的做到O(n)。

【在 a********m 的大作中提到】
: 感觉不对。 压缩的话每次查找接触的块是lgm(m是块数，算是n的函数，理论上不是常
: 数)
a********m
发帖数: 15480
60
扫两次怎么做？

【在 d*******l 的大作中提到】
: 这个在上面给的链接和算法导论上都有相关的分析，确实是n的函数，但增长非常慢，
: 对于我们可以想得到的n，几乎不会超过5。实际运行中效果也确实如此。关键题目说一
: 次扫描就要出来，那这样做比较方便，否则扫两次就能很直接的做到O(n)。
相关主题
● 大家帮我看看这个程序哪里有问题啊！！● 一道复杂的题，求解法
● F家伪面经，求bless● Random Array number, Find longest consecutive sequence
● (已解决，code错了) online judge 有的时候会有点小bug吗？● 砸了面试，发面题
进入JobHunting版参与讨论
P**********c
发帖数: 3417
61
建一个包括所有数range的array, 对每个数标记是否存在，然后扫一遍这个大array?
不过这个就是O(range), 不是O(n)

【在 a********m 的大作中提到】
: 扫两次怎么做？
a********m
发帖数: 15480
62
这个肯定太基本。关键就是怎么不扫描[min,max]的所有数.

【在 P**********c 的大作中提到】
: 建一个包括所有数range的array, 对每个数标记是否存在，然后扫一遍这个大array?
: 不过这个就是O(range), 不是O(n)
d*******l
发帖数: 338
63
只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
#include
#include
using namespace std;
int count(int a, map &m)
{
if(m[a] > 1)
return m[a];
else if(!m[a+1])
return 1;
m[a] = 1 + count(a+1, m);
return m[a];
}
void solve(int a[], int n)
{
map m;
int i;
for(i = 0; i < n; i++)
m[a[i]] = 1;
int mx = 0, p;
for(i = 0; i < n; i++) {
int t = count(a[i], m);
if(t > mx) {
mx = t;
p = a[i];
}
}
for(i = 0; i < mx; i++)
cout << p + i << " ";
cout << endl;
}

【在 a********m 的大作中提到】
: 这个肯定太基本。关键就是怎么不扫描[min,max]的所有数.
P**********c
发帖数: 3417
64
map不是hashmap啊。map的插入和查找都是O(lgn). 就算插入查找都是O(1)，你这个也不是O(n), 这个要看map access
不存在的key的behavior。这种情况下它会插入一个新的key的，插入一个key么至少就是O(1)。所以你在不停的判断
m[a+1]的时候，map的size最终会涨到这组数的range, 同时时间复杂度也涨到O(range)了. hash_map有同样的问题。
hash_map也是从最底层实现起来的，它不是一个magical的只存n个数就可以O(n) access m(m>>n)个值的工具。

【在 d*******l 的大作中提到】
: 只是用C++编写的，如果把map看做hashmap的话，复杂度就是O(n)。
: #include
: #include
: using namespace std;
: int count(int a, map &m)
: {
: if(m[a] > 1)
: return m[a];
: else if(!m[a+1])
: return 1;
b******c
发帖数: 70
65
#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;
}

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
r******n
发帖数: 170
66
这里有解答：
http://dzmitryhuba.blogspot.com/2011/02/longest-consecutive-ele

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
d*******l
发帖数: 338
67
C++里不是没有标准的hash_map实现吗，想成hashmap就行。
至于你后面的分析我就看不懂了，如果你说的是数据结构的问题，那存n个元素的
hashmap可以做到O(n)空间，插入删除查找都是O(1)（期望，平摊），这点我挺确定的
。所以不妨把每一次访问map都看作是访问数组，就是O(1)。这样的话平均每个元素访
问map的次数不超过3次，就是O(n)的啊

也不是O(n), 这个要看map access
就是O(1)。所以你在不停的判断
range)了. hash_map有同样的问题。
access m(m>>n)个值的工具。

【在 P**********c 的大作中提到】
: map不是hashmap啊。map的插入和查找都是O(lgn). 就算插入查找都是O(1)，你这个也不是O(n), 这个要看map access
: 不存在的key的behavior。这种情况下它会插入一个新的key的，插入一个key么至少就是O(1)。所以你在不停的判断
: m[a+1]的时候，map的size最终会涨到这组数的range, 同时时间复杂度也涨到O(range)了. hash_map有同样的问题。
: hash_map也是从最底层实现起来的，它不是一个magical的只存n个数就可以O(n) access m(m>>n)个值的工具。
d*******l
发帖数: 338
68
这个不错，扫一遍就出来了，很严谨的O(n)。

【在 b******c 的大作中提到】
: #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;
a********m
发帖数: 15480
69
这个不对。
ht[a[i]] = newCount;
ht[a[i]+c1] = newCount;
ht[a[i]-c2] = newCount;

【在 b******c 的大作中提到】
: #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;
d*******l
发帖数: 338
70
刚才想了几个例子，到没发现有什么问题。哪种情况会有问题？

【在 a********m 的大作中提到】
: 这个不对。
: ht[a[i]] = newCount;
: ht[a[i]+c1] = newCount;
: ht[a[i]-c2] = newCount;
相关主题
● 砸了面试，发面题● 好挫的F家面经
● C++问题3● 大牛来做一下这道题
● leetcode-- scramble string● 请教一道题
进入JobHunting版参与讨论
a********m
发帖数: 15480
71
试了一下，似乎是可以。永远保存边界是对的。可是还是有点不放心，还需要再想想。

【在 d*******l 的大作中提到】
: 刚才想了几个例子，到没发现有什么问题。哪种情况会有问题？
d*******l
发帖数: 338
72
我觉得逻辑上是对的，只要别有重复插入就行。这一点代码里有体现。

【在 a********m 的大作中提到】
: 试了一下，似乎是可以。永远保存边界是对的。可是还是有点不放心，还需要再想想。
a********m
发帖数: 15480
73
重复插入不怕，反正能查出来。

【在 d*******l 的大作中提到】
: 我觉得逻辑上是对的，只要别有重复插入就行。这一点代码里有体现。
b******c
发帖数: 70
74
I want to make the code shorter so removed the check

【在 a********m 的大作中提到】
: 试了一下，似乎是可以。永远保存边界是对的。可是还是有点不放心，还需要再想想。
d*******l
发帖数: 338
75
我觉得你的是对的，因为如果排除了重复插入的话，新插入的元素左右两边肯定是某个
group的边界，所以只考虑边界应该是安全的。甚至你代码中h[a[i]] = newCount都是
不必要的。
我的想法是第一遍先把所有数都放进map，第二遍扫描的时候求当前的数向右连续多长
，并更新所有经过的数对应的值。每个数对应的值最多只求一遍，所以每个数访问map
的次数平均就2－3次，应该也是O(n)的。

【在 b******c 的大作中提到】
: I want to make the code shorter so removed the check
g*****k
发帖数: 623
76
似乎不对，
举个例子吧，假设有2个区段，[m..i], [i+2..j]
并且下一步处理 i+1和j-1
处理i+1将使得ht[m]=ht[j]=j-m+1
但是处理j-1的时候，假设ht[j-2]=t(some old value)
之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
束。

#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;
}

【在 b******c 的大作中提到】
: #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;
d*******l
发帖数: 338
77
这个就是重复插入的问题，因为如果已经有区间[i+2, j]，那j-1肯定已经插入过了。
他的代码中对于已经存在于map中的元素直接continue了。

【在 g*****k 的大作中提到】
: 似乎不对，
: 举个例子吧，假设有2个区段，[m..i], [i+2..j]
: 并且下一步处理 i+1和j-1
: 处理i+1将使得ht[m]=ht[j]=j-m+1
: 但是处理j-1的时候，假设ht[j-2]=t(some old value)
: 之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
: 束。
:
: #include
: #include
a********m
发帖数: 15480
78
假设新的数不在hash里面。左面的如果有值就肯定是结束。右面是开始。

【在 g*****k 的大作中提到】
: 似乎不对，
: 举个例子吧，假设有2个区段，[m..i], [i+2..j]
: 并且下一步处理 i+1和j-1
: 处理i+1将使得ht[m]=ht[j]=j-m+1
: 但是处理j-1的时候，假设ht[j-2]=t(some old value)
: 之后ht[j]=j-m+1+t是错误的，因为hast table ht[i]无法区分是以i开始，还是以i结
: 束。
:
: #include
: #include
g*****k
发帖数: 623
79
收到

【在 d*******l 的大作中提到】
: 这个就是重复插入的问题，因为如果已经有区间[i+2, j]，那j-1肯定已经插入过了。
: 他的代码中对于已经存在于map中的元素直接continue了。
g*****k
发帖数: 623
80
呵呵，是地

【在 a********m 的大作中提到】
: 假设新的数不在hash里面。左面的如果有值就肯定是结束。右面是开始。
相关主题
● Divide num list into grp of consecutive nums with order preserved● Unique Binary Search Trees的变形
● Question:Given a array,find out if there exist a subarray such its sum is zero● leetcode N-Queens II 我的c++要400多毫秒
● 问个anagram的问题● topcoder- strange country problem.
进入JobHunting版参与讨论
j*****p
发帖数: 108
81

Map不是hashtable吧？ 所以find不是O(1)操作

【在 d*******l 的大作中提到】
: 这个不错，扫一遍就出来了，很严谨的O(n)。
g**********y
发帖数: 14569
82
赞！关键点找得很好。

【在 b******c 的大作中提到】
: #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;
d*******l
发帖数: 338
83
额，前面说了C++标准库没有hashmap的实现所以就用map了，想成hashmap就行了。方法
都是一样的。

【在 j*****p 的大作中提到】
:
: Map不是hashtable吧？ 所以find不是O(1)操作
k****n
发帖数: 369
84
union-find set.
For each input x, first set p[x] = x; then union x with x-1 and x+1 if
available
During union update, keep set size and update max size.
In one go and the time complexity is O(n*alpha(n)) ~~ O(n)

【在 r******n 的大作中提到】
: 从careercup上看的，
: Given an array of random numbers. Find the longest consecutive sequence.
: For ex
: Array 100 3 200 1 2 4
: Ans 1 2 3 4
: Array 101 2 3 104 5 103 9 102
: Ans 101 102 103 104
: Can we do it in one go on array using extra space??
: 觉得一次扫描怎么也作不出来吧？能想到的就是建个hash表，然后再扫描一次保存最长
: 的连续数组。
k****n
发帖数: 369
85

int *p;
int *sz;
void init() {
p = (int *) malloc(sizeof(int)*(MAX_INT));
sz = (int *) malloc(sizeof(int)*(MAX_INT));
memset(p, 0, sizeof(int)*MAX_INT);
memset(sz, 0, sizeof(int)*MAX_INT);
}
void clean() {
free(p); free(sz);
}
int find(int x) {
if (x == p[x]) return x;
p[x] = find(p[x]);
return p[x];
}
int union(int x, int y) {
int rx = find(x);
int ry = find(y);
if (rx == ry) {
return sz[rx];
} else if (sz[rx] > sz[ry]) {
p[ry] = rx;
sz[rx] += sz[ry];
return sz[rx];
} else {
p[rx] = ry;
sz[ry] += sz[rx];
return sz[ry];
}
}
int eat(int x) {
if (p[x] != 0) return;
p[x] = x; sz[x] = 1;
union(x, x-1);
return union(x, x+1);
}
int scan(int a[], int n) {
init();
int i;
int max = 0;
for (i=0; i int m = eat(a[i]);
if (m > max) max = m;
}
clean();
return max;
}

【在 k****n 的大作中提到】
: union-find set.
: For each input x, first set p[x] = x; then union x with x-1 and x+1 if
: available
: During union update, keep set size and update max size.
: In one go and the time complexity is O(n*alpha(n)) ~~ O(n)
P**********c
发帖数: 3417
86
嗯，我看得不太仔细，你的解法应该是对的。

【在 d*******l 的大作中提到】
: C++里不是没有标准的hash_map实现吗，想成hashmap就行。
: 至于你后面的分析我就看不懂了，如果你说的是数据结构的问题，那存n个元素的
: hashmap可以做到O(n)空间，插入删除查找都是O(1)（期望，平摊），这点我挺确定的
: 。所以不妨把每一次访问map都看作是访问数组，就是O(1)。这样的话平均每个元素访
: 问map的次数不超过3次，就是O(n)的啊
:
: 也不是O(n), 这个要看map access
: 就是O(1)。所以你在不停的判断
: range)了. hash_map有同样的问题。
: access m(m>>n)个值的工具。
I******k
发帖数: 378
87
是nlogn吧

【在 d*******l 的大作中提到】
: 这个不错，扫一遍就出来了，很严谨的O(n)。
h***i
发帖数: 1970
88
tr1::unordered_map

【在 d*******l 的大作中提到】
: C++里不是没有标准的hash_map实现吗，想成hashmap就行。
: 至于你后面的分析我就看不懂了，如果你说的是数据结构的问题，那存n个元素的
: hashmap可以做到O(n)空间，插入删除查找都是O(1)（期望，平摊），这点我挺确定的
: 。所以不妨把每一次访问map都看作是访问数组，就是O(1)。这样的话平均每个元素访
: 问map的次数不超过3次，就是O(n)的啊
:
: 也不是O(n), 这个要看map access
: 就是O(1)。所以你在不停的判断
: range)了. hash_map有同样的问题。
: access m(m>>n)个值的工具。
m**q
发帖数: 189
89
mark

【在 b******c 的大作中提到】
: #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;
c*********t
发帖数: 2921
90
Hi getback,
你说的 bit vector是不是就是C++ STL里的bitset?
你用bit vector,解决这个题，要用到多大的extra space? 我的理解是我们不知道数的
范围，所以如果最大的数有可能是2^31-1,是不是这个bit vector也用可能要有这么大
？这样的话，占用的空间太大了。感觉扫描这个bit vector的时间也不是O(n),而是等
于最大的数。
谢谢！

【在 g*****k 的大作中提到】
: 如果要求O(n)的算法，那么我能想到的也就是用bit vector再扫描一次了。
: 这里的using extra space是指没有限制吗？
相关主题
● 给定字符串，求其不出现重复字符的子字符串的最大长度● F家伪面经，求bless
● 问个MSFT的题● (已解决，code错了) online judge 有的时候会有点小bug吗？
● 大家帮我看看这个程序哪里有问题啊！！● 一道复杂的题，求解法
进入JobHunting版参与讨论
h**********8
发帖数: 267
91
mark

【在 b******c 的大作中提到】
: #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;
g*****k
发帖数: 623
92
是的，你说的是对的，大家已经讨论过了。你看看大家的讨论。

【在 c*********t 的大作中提到】
: Hi getback,
: 你说的 bit vector是不是就是C++ STL里的bitset?
: 你用bit vector,解决这个题，要用到多大的extra space? 我的理解是我们不知道数的
: 范围，所以如果最大的数有可能是2^31-1,是不是这个bit vector也用可能要有这么大
: ？这样的话，占用的空间太大了。感觉扫描这个bit vector的时间也不是O(n),而是等
: 于最大的数。
: 谢谢！
s******n
发帖数: 226
93
在java里， 我把a[i]当key， 一个node当value， node里存prev和next，true/false
表示有还是没有，这样就成了一个链表，每扫一个数，向前走到头，向后走到头，记录
长度，顺便在map里删掉，这样就O（n）了。
多多指教
h******n
发帖数: 68
94
赞，学习了，mark

【在 b******c 的大作中提到】
: #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;
n*******w
发帖数: 687
95
跑了随机1000个元素的例子，取值范围为0-99。结果不对。
问题可能在于，得到一个sequence在hashmap里会残留下一些entry，导致接下来处理重
复元素出错。
比如残留的entry里有两个sequence [0 10] [6 12]。hashmap里会存在4个entry [0,11
] [10, 11] [6,7] [12 7]。如果下一个元素是11。合并两个sequence，得到长度为19
的sequence。其实不存在。
问题在于[12,7]是以12结尾的长度为7的序列。而以后访问的时候并不知道，把它当做
12开始长度为7的序列。而残留的entry里有很多这样的sequence，导致整个结果不对。

【在 b******c 的大作中提到】
: #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;
f*******t
发帖数: 7549
96
把map当作hashmap用，可处理重复的数字
#include
#include
using namespace std;
int main()
{
map hashmap;

int arr[] = { 100, 3, 200, 3, 1, 2, 4, 101, 6, 99, 7, 102, 105, 104,
103
};

int maxLen = 0;
int maxStart = -1;
for(int i = 0; i < sizeof(arr) / sizeof(int); i++) {
map::iterator it = hashmap.find(arr[i]);
if(it == hashmap.end()) {
map::iterator left = hashmap.find(arr[i] - 1);
map::iterator right = hashmap.find(arr[i] + 1);
int leftoffset = (left == hashmap.end() ? 0 : hashmap[arr[i]
- 1
]);
int rightoffset = (right == hashmap.end() ? 0 :
hashmap[arr[i] +
1]);
int newMax = leftoffset + rightoffset + 1;
if(newMax > maxLen) {
maxLen = newMax;
maxStart = arr[i] - leftoffset;
}

// Update left end and right end
hashmap[arr[i] - leftoffset] = newMax;
hashmap[arr[i] + rightoffset] = newMax;
}
else // Ignore duplicate numbers
continue;
}

printf("Start from %d, length = %d\n", maxStart, maxLen);

return 0;
}
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 大家帮我看看这个程序哪里有问题啊！！● 好挫的F家面经
● F家伪面经，求bless● 大牛来做一下这道题
● (已解决，code错了) online judge 有的时候会有点小bug吗？● 请教一道题
● 一道复杂的题，求解法● Divide num list into grp of consecutive nums with order preserved
● Random Array number, Find longest consecutive sequence● Question:Given a array,find out if there exist a subarray such its sum is zero
● 砸了面试，发面题● 问个anagram的问题
● C++问题3● Unique Binary Search Trees的变形
● leetcode-- scramble string● leetcode N-Queens II 我的c++要400多毫秒
相关话题的讨论汇总
话题: int话题: newcount话题: ht话题: map话题: max

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑