g***j
发帖数: 1275 | 1 Given an unsorted array of integers, find the length of the longest
consecutive elements sequence.
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
Your algorithm should run in O(n) complexity.
我在网上看到了几段code，用到了set或者map，每次要在set或者map里面找到，然后删
掉，我想问，这样的code时间是n么？find in a set难道不是logn么？当然也有用到
map的，我觉得找元素都是logn啊，那么最终的时间就是nlogn啊，比如如下code
class Solution {
public:
int longestConsecutive(vector &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
mapmp;
for (int i=0;i
mp[num[i]]=true;
}
int res=0;
for (int i=0;i
int mx=1;
int fd = num[i];
mp.erase(num[i]);
while (mp.find(fd+1)!=mp.end()){
mx++;
mp.erase(fd+1);
fd++;
}
fd = num[i];
while (mp.find(fd-1)!=mp.end()){
mx++;
mp.erase(fd-1);
fd--;
}
if (mx>res){res=mx;}
}
return res;
}
}; | r*******e
发帖数: 7583 | 2 set/map不一定是ordered，看实际需要
像这个例子里的，用hash_set/hash_map实现就是O(1)查找了
length
【在 g***j 的大作中提到】
: Given an unsorted array of integers, find the length of the longest
: consecutive elements sequence.
: For example,
: Given [100, 4, 200, 1, 3, 2],
: The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length
: Your algorithm should run in O(n) complexity.
: 我在网上看到了几段code，用到了set或者map，每次要在set或者map里面找到，然后删
: 掉，我想问，这样的code时间是n么？find in a set难道不是logn么？当然也有用到
: map的，我觉得找元素都是logn啊，那么最终的时间就是nlogn啊，比如如下code
: class Solution {
| s**********r
发帖数: 8153 | |
|
