l**********g
发帖数: 426 | 1 数组 3, 5,1, 8, 9, 7, 0, 2
找到 3, 1, 0, 2 ----最长序列
要求复杂度好于 O(nlog(n))
有hashmap记录间隔的解法，写起来蛮复杂。
大侠指点。 | l*********8
发帖数: 4642 | 2 sort first
then scan the sorted array to find the maximum sequence?
【在 l**********g 的大作中提到】
: 数组 3, 5,1, 8, 9, 7, 0, 2
: 找到 3, 1, 0, 2 ----最长序列
: 要求复杂度好于 O(nlog(n))
: 有hashmap记录间隔的解法，写起来蛮复杂。
: 大侠指点。
| t**********h
发帖数: 2273 | 3 bitmap？如果大概知道数列range的话
这里有个问题，input的array允许有重复吗？不允许，那么bitmap很好用。如果如需，
那最长序列怎么算呢？是相同的都输出吗？还是相同的只输入一个？还是说有重复，直
接报错？
假设input不允许重复，或者允许重复，但是遇到重复，skip掉重复的。
初始化每一位都为0
然后loop一边 O（n），遇到一个数字，检查bit是否为0，是的话就设为1。（允许重复
的话，已经是1的话就不管）。
扫完后，再扫一遍，检查最长的连续的1串。
当然这个算法不通用，只是说一个想法，抛砖引玉，大牛来指点咯
【在 l**********g 的大作中提到】
: 数组 3, 5,1, 8, 9, 7, 0, 2
: 找到 3, 1, 0, 2 ----最长序列
: 要求复杂度好于 O(nlog(n))
: 有hashmap记录间隔的解法，写起来蛮复杂。
: 大侠指点。
| Z*****Z
发帖数: 723 | 4 ding这个
【在 t**********h 的大作中提到】
: bitmap？如果大概知道数列range的话
: 这里有个问题，input的array允许有重复吗？不允许，那么bitmap很好用。如果如需，
: 那最长序列怎么算呢？是相同的都输出吗？还是相同的只输入一个？还是说有重复，直
: 接报错？
: 假设input不允许重复，或者允许重复，但是遇到重复，skip掉重复的。
: 初始化每一位都为0
: 然后loop一边 O（n），遇到一个数字，检查bit是否为0，是的话就设为1。（允许重复
: 的话，已经是1的话就不管）。
: 扫完后，再扫一遍，检查最长的连续的1串。
: 当然这个算法不通用，只是说一个想法，抛砖引玉，大牛来指点咯
| C***U
发帖数: 2406 | 5 这个就是要求事先知道range是O(n)的 时间才是O(n)
也可以用类似 查找不在数列中的最小正整数 的方法
【在 t**********h 的大作中提到】
: bitmap？如果大概知道数列range的话
: 这里有个问题，input的array允许有重复吗？不允许，那么bitmap很好用。如果如需，
: 那最长序列怎么算呢？是相同的都输出吗？还是相同的只输入一个？还是说有重复，直
: 接报错？
: 假设input不允许重复，或者允许重复，但是遇到重复，skip掉重复的。
: 初始化每一位都为0
: 然后loop一边 O（n），遇到一个数字，检查bit是否为0，是的话就设为1。（允许重复
: 的话，已经是1的话就不管）。
: 扫完后，再扫一遍，检查最长的连续的1串。
: 当然这个算法不通用，只是说一个想法，抛砖引玉，大牛来指点咯
| t**********h
发帖数: 2273 | 6 “也可以用类似 查找不在数列中的最小正整数 的方法”
zkss这个思路，可以吗？
【在 C***U 的大作中提到】
: 这个就是要求事先知道range是O(n)的 时间才是O(n)
: 也可以用类似 查找不在数列中的最小正整数 的方法
| z********i
发帖数: 568 | 7 1. 找到中间值（MEDIAN）m in time O(n)
2. 跟中间值比较，分为两半。检查小的这一半有多少in time O(n)。如果正好m个数，
继续大的这一半的收索。否则，继续小的这一半的收索。
复杂度：T(n)=T(n/2)+n--->T(n)=O(n).
例子：3 5 1 8 9 7 0 2
1. median: 3
2. >3: 5 8 9 7
<3: 1 0 2(3个数)
3. continue search 5 8 9 7.
4. median 7.
5. >7: 8 9
<7: 5(1个数<7-4=3)
6. continue search 5.
7. >5:
<5: (0个数<5-4=1)
8. return the last correct median 3.
9. search all the array again to find numbers not greater than 3.
Assumption: no duplicated numbers.
【在 l**********g 的大作中提到】
: 数组 3, 5,1, 8, 9, 7, 0, 2
: 找到 3, 1, 0, 2 ----最长序列
: 要求复杂度好于 O(nlog(n))
: 有hashmap记录间隔的解法，写起来蛮复杂。
: 大侠指点。
| s*******f
发帖数: 1114 | 8 no need 3. continue search 5 8 9 7.---because the answer is 0123
u also need get the list that across 3.
【在 z********i 的大作中提到】
: 1. 找到中间值（MEDIAN）m in time O(n)
: 2. 跟中间值比较，分为两半。检查小的这一半有多少in time O(n)。如果正好m个数，
: 继续大的这一半的收索。否则，继续小的这一半的收索。
: 复杂度：T(n)=T(n/2)+n--->T(n)=O(n).
: 例子：3 5 1 8 9 7 0 2
: 1. median: 3
: 2. >3: 5 8 9 7
: <3: 1 0 2(3个数)
: 3. continue search 5 8 9 7.
: 4. median 7.
|
| f*******t
发帖数: 7549 | 9 以前讨论过，有O(n) time&space解法 | l*********8
发帖数: 4642 | 10 It seems that I don't fully understand the reqirement of this question.
Why can't we just sort the array first? It's very easy to find the maximum
sequence.
Can someone explain it to me? Thanks. | | | w****x
发帖数: 2483 | 11 用hashtable保存value->index pair, 用bool数组记录对应index是否访问过, 遍历大
数组, 对每个值向两边延伸,更新hashtable和bool数组, 这样disjoint的segment就一
个个浮现出来了, O(n) | H****r
发帖数: 2801 | 12 Guess it requires substring not subsequence
【在 l*********8 的大作中提到】
: It seems that I don't fully understand the reqirement of this question.
: Why can't we just sort the array first? It's very easy to find the maximum
: sequence.
: Can someone explain it to me? Thanks.
| t********e
发帖数: 143 | 13
Sort is O(nlgn). LZ wants a solution better than that.
【在 l*********8 的大作中提到】
: It seems that I don't fully understand the reqirement of this question.
: Why can't we just sort the array first? It's very easy to find the maximum
: sequence.
: Can someone explain it to me? Thanks.
| w****x
发帖数: 2483 | | j********e
发帖数: 1192 | 15 O(n)时间和O(n)内存的算法可以建立一个link list。
class Node {
int V;
int length;
Node *next;
};
每个数V建一个node，然后point到V-1对应的node
（如果V-1不存在就指向NULL）。通过hashmap，这个可以
O(n)时间内建立起多个链表。
然后对每个Node，开始计算以该node为起点的链表长度，
这个长度也保存在node数据里length。
这个也是O(n)，因为每个节点只需要计算一次。例如下面
例子中，从3开始，一直会经过2,1,0对应的node，同时
就把所有这些node的length计算了，以后就不需要再算，
所以每个node花O(1)时间。
后面就是打印最长的链表了。
【在 l**********g 的大作中提到】
: 数组 3, 5,1, 8, 9, 7, 0, 2
: 找到 3, 1, 0, 2 ----最长序列
: 要求复杂度好于 O(nlog(n))
: 有hashmap记录间隔的解法，写起来蛮复杂。
: 大侠指点。
| l*********8
发帖数: 4642 | 16 看例子是subsequence.
【在 H****r 的大作中提到】
: Guess it requires substring not subsequence
| l*********8
发帖数: 4642 | 17 哦，原来如此。 我以为是a solution at least O(nlogn) ... 谢谢！
【在 t********e 的大作中提到】
:
: Sort is O(nlgn). LZ wants a solution better than that.
| l*********8
发帖数: 4642 | 18 访问了3, 5,1, 8, 9, 7, 0 之后，
hashtable是什么样？
再访问1之后，
hashtable又是什么样？
【在 w****x 的大作中提到】
: 用hashtable保存value->index pair, 用bool数组记录对应index是否访问过, 遍历大
: 数组, 对每个值向两边延伸,更新hashtable和bool数组, 这样disjoint的segment就一
: 个个浮现出来了, O(n)
| H****r
发帖数: 2801 | 19 sorry 看错题了
【在 l*********8 的大作中提到】
: 看例子是subsequence.
| s*******f
发帖数: 1114 | 20 jingo 你狠彪悍！！
//码遍本版
//: 数组 3, 5,1, 8, 9, 7, 0, 2
//: 找到 3, 1, 0, 2 ----最长序列
//: 要求复杂度好于 O(nlog(n))
//i use static linked list here
//change map to hash_map, then O(n)
struct NodeInfo{
int data;
int next;
bool has_pre;
NodeInfo(int d):data(d), next(-1), has_pre(false){ }
NodeInfo(){}
};
vector MaxForSeq(int a[], int len){
vector ret;
vector vn(len);
map mp; //data to index in vector vn
for (int i = 0; i < len; ++i){
if (mp.find(a[i]) == mp.end()){
vn.push_back(NodeInfo(a[i]));
mp[a[i]] = vn.size() - 1;
}
}
for (vector::iterator it = vn.begin(); it != vn.end(); ++it){
if (mp.find(it->data - 1) == mp.end()){
continue;
} else {
it->next = mp[it->data - 1];
vn[mp[it->data - 1]].has_pre = true;
}
}
int max = 0;
int idxmax = -1;
for (vector::iterator it = vn.begin(); it != vn.end(); ++it){
if (!it->has_pre){
int count = 1;
for (int i = it->next; i != -1; i = vn[i].next){
++count;
}
if (count > max){
max = count;
idxmax = it - vn.begin();
}
}
}
for (int i = idxmax; i != -1; i = vn[i].next){
ret.push_back(vn[i].data);
}
return ret;
}
void TestMaxForSeq(){
vector a;
int b[] = {1,3,2};
a = MaxForSeq(b, 3);
int c[] = {3, 5,1, 8, 9, 7, 0, 2};
a = MaxForSeq(c, 8);
}
【在 j********e 的大作中提到】
: O(n)时间和O(n)内存的算法可以建立一个link list。
: class Node {
: int V;
: int length;
: Node *next;
: };
: 每个数V建一个node，然后point到V-1对应的node
: （如果V-1不存在就指向NULL）。通过hashmap，这个可以
: O(n)时间内建立起多个链表。
: 然后对每个Node，开始计算以该node为起点的链表长度，
|
|
