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) + 無(wú)序 -> hash table
具體實(shí)現(xiàn)應(yīng)該學(xué)會(huì)調(diào)用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:考慮這樣一個(gè)聚類(lèi)模型撇叁，在一個(gè)數(shù)軸上有個(gè)無(wú)數(shù)的聚類(lèi)，每個(gè)聚類(lèi)由一個(gè)或多個(gè)數(shù)字組成畦贸，每個(gè)聚類(lèi)的大小由最大元素減去最小元素得到陨闹，每次讀入一個(gè)元素或者會(huì)創(chuàng)造一個(gè)新聚類(lèi)，或者會(huì)和其左右的兩個(gè)聚類(lèi)合并薄坏。這個(gè)模型由map來(lái)實(shí)現(xiàn)趋厉，其映射的關(guān)系是key->length。具體在c++里用unordered_map來(lái)實(shí)現(xiàn)胶坠。
trap1:會(huì)有重復(fù)的數(shù)字
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:會(huì)有重復(fù)的數(shù)字
// 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;
}
