【leetcode】Longest Consecutive Sequence
【leetcode】Longest Consecutive Sequence
阳光岛主
发布于 2019-02-19 11:29:49
发布于 2019-02-19 11:29:49
Question ：
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: 4.
Your algorithm should run in O(n) complexity.
Anwser 1 ：
class Solution {
public:
int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<int, int> hmap;
hmap.clear();
int n = num.size();
for(int i=0; i<n; i++){
//hmap.insert(pair<int, int>(num[i], i));
hmap[num[i]] = i;
}
int ans=0, cnt=0;
map<int, int>::iterator it;
for(int i=0; i<n; i++)
{
int cur = num[i];
it = hmap.find(num[i]); // value
cnt++;
if(it!=hmap.end())
{
map<int, int>::iterator iter;
while(1){
iter = hmap.find(++cur); // to larger value
if(iter == hmap.end())
break;
cnt++;
hmap.erase(iter);
}
cur=num[i];
while(1){
iter = hmap.find(--cur); // to smaller value
if(iter == hmap.end())
break;
cnt++;
hmap.erase(iter);
}
ans = cnt > ans ? cnt : ans;
}
cnt=0; // init to count remaider value of hmap
}
return ans;
}
};注意点：
1） 采用map，value为map_key， index为map_value
2） 按value++， value--查找，找到了则从map移除（erase），减少for循环find的次数
3） for + while，时间复杂度最坏其实为O（n*n），但是仍然编译通过了...
Anwser 2 ：
class Solution {
public:
int getCount(map<int, int> &hmap, int value, bool asc){
int count = 0;
while(hmap.find(value) != hmap.end()){
hmap.erase(value);
count++;
if(asc){
value++;
} else {
value--;
}
}
return count;
}
int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<int, int> hmap;
hmap.clear();
int n = num.size();
for(int i=0; i<n; i++){
//hmap.insert(pair<int, int>(num[i], i));
hmap[num[i]] = i;
}
int ans=0, cnt=0;
for(int i=0; i<n; i++)
{
int count = getCount(hmap, num[i], false) + getCount(hmap, num[i]+1, true);
ans = count > ans ? count : ans;
}
return ans;
}
};注意点：
1） 改进了方法1
2） getCount（）找到则移除，count++，继续寻找下一个
3） count = getCount(hmap, num[i], false) + getCount(hmap, num[i]+1, true); 注意暗红色部分，加1为因为之前num[i]已经被移除了，因此找其上面一个value + 1
Anwser 3 ：
class Solution {
public:
int longestConsecutive(vector<int> &num) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
map<int, int> hmap;
hmap.clear();
int n = num.size();
for(int i=0; i<n; i++){
hmap.insert(pair<int, int>(num[i], 1)); // map will auto sort by key(num[i])
//hmap[num[i]] = 1;
}
int ans = 1; // min init
int pre_k = 0;
int pre_v = 0;
map<int, int>::iterator it;
for(it = hmap.begin(); it != hmap.end(); it++)
{
if(it == hmap.begin()) {
pre_k = it->first;
pre_v = it->second;
continue;
}
if(it->first == pre_k + 1){
it->second = pre_v + 1;
ans = it->second > ans ? it->second : ans;
}
pre_k = it->first;
pre_v = it->second;
}
return ans;
}
};注意点：
1） 方法2的进一步改进
2） 此方法最大的利用了map自动根据key（num[i]）排序，且value设为了1（起始值）
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2013年05月01日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读