有些人总喜欢为了些虚无的honor而战# PDA - 掌中宝
g*j
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
}
int res=0;
for (int i=0;i
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;
}
};
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
// Start typing your C/C++ solution below
// DO NOT write int main() function
map
for (int i=0;i
}
int res=0;
for (int i=0;i
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;
}
};
