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.
int longestConsecutive(int* nums, int numsSize) {
}
解法1: O(n) + 无序 -> hash table
具体实现应该学会调用unordered_map
| functions |
|---|
| find() |
| end() |
//
// main.cpp
// leetcode
//
// Created by YangKi on 15/11/09.
// Copyright © 2015年 YangKi. All rights reserved.
//
#include<cstdlib>
#include<iostream>
#include<vector>
#include<unordered_map>//!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
using namespace std;
class Solution
{
public:
int longestConsecutive(vector<int>& nums)
{
if( nums.empty()==true ) return 0;
unordered_map<int, bool> used;
for ( int i: nums ) used[i] = false;
int longest = 1;
for(int i: nums)
{
if (used[i] == true) continue;
int length=1;
used[i]=true;
for(int j=i+1; used.find(j)!=used.end(); j++)
{
length++;
used[j]=true;
}
for(int j=i-1; used.find(j)!=used.end(); j--)
{
length++;
used[j]=true;
}
if(length>longest) longest=length;
}
return longest;
}
};
int main()
{
Solution *s=new Solution();
vector<int>v={};
printf("%d\n", s->longestConsecutive(v));
return 0;
}
解法2:考虑这样一个聚类模型，在一个数轴上有个无数的聚类，每个聚类由一个或多个数字组成，每个聚类的大小由最大元素减去最小元素得到，每次读入一个元素或者会创造一个新聚类，或者会和其左右的两个聚类合并。这个模型由map来实现，其映射的关系是key->length。具体在c++里用unordered_map来实现。
trap1:会有重复的数字
trap2:only modify the length of low and high
//
// main.cpp
// leetcode
//
// Created by YangKi on 15/11/10.
// Copyright © 2015年 YangKi. All rights reserved.
//
#include<cstdlib>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
class Solution
{
public:
int longestConsecutive(vector<int>& nums)
{
int size = nums.size();
int l=1;
unordered_map<int, int>map;
for (int i=0; i<size ; i++)
{
if(map.find(nums[i])!= map.end()) continue; //trap1:会有重复的数字
// map does not contain nums[size] yet
map[ nums[i] ]=1;//at least a one element cluster
//have to merge?
if(map.find( nums[i]-1 )!=map.end())//can merge the left part
{
l = max( clusterMerge(map, nums[i]-1, nums[i]), l);
}
if(map.find( nums[i]+1 )!=map.end())//can merge the right part
{
l = max( clusterMerge(map, nums[i], nums[i]+1), l);
}
}
return size == 0? 0: l;
}
private:
int clusterMerge(unordered_map<int , int> &map, int left, int right)// attention:!!!!!!use &
{
int low=left-map[left]+1;
int high=right+map[right]-1;
int length = high-low+1;
map[low]=length;//trap2:only modify the length of low and high
map[high]=length;
return length;
}
};
int main()
{
Solution *s=new Solution();
vector<int>v={3,2,4,1};
printf("%d\n", s->longestConsecutive(v));
return 0;
}
