题目：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.
分析：给定一个没有排序的整型数组，，找出其中最长的连续数字的长度，要求复杂度为o(n)。这题难度不高，我直接先排序再查找。给出三种解法，第一种解法是我自己设计，后面两种是参考网上比较好的解法，学习学习。
代码：
<span style="font-size:14px;">#include "stdafx.h"#include <vector>#include <unordered_map>#include <algorithm>#include <iostream>using namespace std;class Solution{public://时间O(n)int longstConsecutiveSequence(vector<int> &num){//先排序sort(num.begin(), num.end(),less<int>());int max = 1; //记录最长的连续个数int n = 1; //记录单次连续的个数bool flag = false; //标识是否连续int temp = -1; //记录前面一个元素vector<int>::const_iterator cit;for (cit = num.begin();cit != num.end();cit++){if (flag){if (*cit == (temp + 1)){n++;}else{flag = false;if (n>max){max = n;}n = 1;}}else{flag = true;if (*cit == (temp + 1)){n++;}}temp = *cit;}//可能最后一个连续的最大if (n>max){max = n;}return max;}int longstConsecutiveSequence2(vector<int> &num){unordered_map<int, bool> used;vector<int>::iterator it;//初始化，赋值到map中for (it = num.begin();it != num.end();it++) used[*it] = false;int longest=0;for (it = num.begin();it != num.end();it++){if (used[*it]) continue;int length = 1;used[*it] = true;//向两边查找for (int j = *it + 1; used.find(j) != used.end(); ++j) {used[j] = true;++length;}for (int j = *it – 1; used.find(j) != used.end(); –j) {used[j] = true;++length;}//取最大的longest = max(longest, length);}return longest;}int longstConsecutiveSequence3(vector<int> &num){unordered_map<int, int> map;int size = num.size();int l = 1;for (int i = 0; i < size; i++) {if (map.find(num[i]) != map.end()) continue;map[num[i]] = 1;if (map.find(num[i] – 1) != map.end()) {l = max(l, mergeCluster(map, num[i] – 1, num[i]));}if (map.find(num[i] + 1) != map.end()) {l = max(l, mergeCluster(map, num[i], num[i] + 1));}}return size == 0 ? 0 : l;}private:int mergeCluster(unordered_map<int, int> &map, int left, int right) {int upper = right + map[right] – 1;int lower = left – map[left] + 1;int length = upper – lower + 1;map[upper] = length;map[lower] = length;return length;}};int _tmain(int argc, _TCHAR* argv[]){vector<int> a;a.push_back(5);a.push_back(6);a.push_back(1);a.push_back(2);a.push_back(3);a.push_back(22);a.push_back(23);a.push_back(24);a.push_back(25);a.push_back(7);a.push_back(100);Solution s;int rtn = s.longstConsecutiveSequence2(a);cout << rtn << endl;system("pause");return 0;}</span>个人感觉第二种比较好，易于理解。
今天刷了两题LeetCode，花了好长时间，瞬间感觉资质太平庸了。。。。。
不义而富且贵，于我如浮云。
