longest consecutive sequences
看到July群里有人提问，大家讨论很激烈。
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.
一开始乍看这题，首先反应就是sort然后遍历就可以了，但是时间复杂度不行。线性的算法貌似都没有思路，后来看到有人说radix sort，我一直都没反应过来，看了那些sort，居然
把这茬忘记了，于是回顾DS的相关课件，发现有个算法复杂度没弄明白，PPT写O(d(n+rd)) 但是我感觉就是O(d(n+r)), 其中d是最大数的位数，r是基数(10), 每一躺就是遍历链表，把他丢到当前位数合适的桶里，
然后把链表实现的队列链接起来，n+r感觉是，不知道为啥。。。
后来又有一路hash流，感觉hash一般都不会是最好的算法，因为一个hash函数的非普遍适用性使得一次查找O(1)值得怀疑，但是已经没有其他更好的方案了o(╯□╰)o
于是想到先建立hash，然后逐个看相邻的是否在里面，也是因为有频繁的查找，才想到hash，但是发现直接用
3的序列更新在1 2那里，没有传递到0那里，导致出错，而且可能会出现重复合并等等，所以加一个left right 逻辑变量，判断是否已经合并过了，于是可以设计代码了
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <math.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#include <iomanip>
#include <unordered_map>
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define read freopen("in.txt","r",stdin)
#define write freopen("out.txt","w",stdout)
using namespace std;
struct length
{
int count;
bool left;
bool right;
};
int longestConsecutive(vector<int> &num) {
unordered_map<int,length> map;
length l;
l.count=1;l.left=false;l.right=false;
for(int i=0;i<num.size();i++)
{
if(map.find(num.at(i))==map.end())
map[num.at(i)]=l;
}
unordered_map<int,length>::iterator it;
for(it=map.begin();it!=map.end();it++)
{
if(it->second.left==false)
{
if(map.find(it->first-1)!=map.end() && map[it->first-1].right==false)
{
int sumlength=map[it->first].count+map[it->first-1].count;
map[it->first].count=sumlength;
map[it->first-1].count=sumlength;
it->second.left=true;
map[it->first-1].right=true;
}
}
if(it->second.right==false)
{
if(map.find(it->first+1)!=map.end() && map[it->first+1].left==false)
{
int sumlength=map[it->first].count+map[it->first+1].count;
map[it->first].count=sumlength;
map[it->first+1].count=sumlength;
it->second.right=true;
map[it->first+1].left=true;
}
}
}
it=map.begin();
int max=it->second.count;
for(it=map.begin();it!=map.end();it++)
{
if(max<it->second.count)
max=it->second.count;
}
return max;
}
int main()
{
int a[]={1,3,5,2,4};
vector<int> num(&a[0],&a[5]);
cout<<longestConsecutive(num)<<endl;
return 0;
}
但是发现leetcode跑出来居然和local的不一样，我也没用静态变量啊，还有全局变量，而且之前直接贴本地完整代码，还被管理员封了贴o(╯□╰)o
目前还不知道为何。。。 (问题找到了，leetcode的g++ 编译选项没有 std=c++0x, 不支持C++11，unordered_map是C++11里的，我用的VS其实是支持了C++11，而我也没办法改后台编译的参数选项，
于是出现了不可预料的结果，于是按照管理员说法改成map，居然还过了，这个已经不是线性复杂度，是O(nlon)了，leetcode看来时间复杂度不像ACM那么严: ) 而且管理员说还有更elegant的算法，不需要用到
类似hash这种复杂的数据结构，我目前想到的只有radix sort，这个也是线性的，输入是int，最多丢12次桶，所以还是线性复杂度)
另外还有些C++知识总结：
C++ class构造函数用冒号初始化的时候顺序是成员变量定义的顺序，和初始化顺序无关，所以会有些陷阱题
class A
{
int n1;
int n2;
A(): n2(1) n1(n2+1)
}
这里面其实n1先初始化，但n2未初始化，是野值，于是n1也是野值，n2=1sizeof作用于一个内部空的结构体返回多少字节
答案是1 不是0， 试想下，如果是0，这个结构体不占空间，那我定义的一个这个对象存在那里，岂不是不存在了？怎么获取他的地址，已经如何判断两个对象哪个是哪个？
虽然这个确实不是常规知识，但是通过逻辑思考，后面如何使用这些变量，可以推测出不为0，VS中是认为1的。
另外还有之前和高富帅想leetcode 通过率最低的一道题，判断二维平面 共线最多的点，想到用hash提高查找效率，但是一条直线
是两个参数决定的，不可能降为1个，于是想有没有两个自变量的hash函数？ 一般都是一个变量，作为key来hash的？
还看到剑指Offer有道题目是说，数组的数合并为一个数的最小数是多少?
这个感觉思路就是先看第一位，如果各不相同，就直接sort第一位就解决了，否则，对于第一位有重复的 再看，如果两两个重复，就继续看两个数的下一位，一直下去，如果多个数的话，就有点麻烦了，
排列情况比较多，还要看他的各位和其他数位数的关系，有点乱。。。感觉目前有的思路是这样。。。