leecode 解题总结：128. Longest Consecutive Sequence

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>using namespace std;/*问题: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)。如果允许排序，那么闲排序，然后从初始部分向后遍历，然后找到最大连续元素长度。如果用统计排序，遍历一遍元素，把元素i放在对应的位置上。遍历完了之后，凡是A[i] > 0，则表示元素i存在，初始时，设置最大连续子序列长度为0，每当发现如果下一个元素为A{i]为0，则统计之前的最大连续子序列长度，如果大于最大连续子序列长度就更新最大连续子序列的值。如果统计排序可以用的话，那其实直接用位图来做也是可以的。由于vector存入100万就会崩溃，必定不能开辟这么大的数据。但是这样的会提前开辟需要知道里面的最大值，直接先遍历一遍，得到最大值，然后用位图。而且实际上应该不允许有负数的。否则位图没办法表示，还得获取最小值。如果最小值小于0，还得为位图增加偏移量。肯定还需要添加偏移量后，实际长度会溢出，最好用long long实在不行直接初始化长度为: INT_MAX + INT_MAX + 1;反正整形只有这么多输入:6(数组元素个数)100 4 200 1 3 26100 4 200 3 101 10251 3 5 7 92-1000000 1000000-1000000 -500000-2147483648 2147483647输出:431111报错:Runtime Error Message:terminate called after throwing an instance of 'std::bad_alloc'  what():  std::bad_allocLast executed input:[2147483646,-2147483647,0,2,2147483644,-2147483645,2147483645]果然，似乎直接统计排序没有用，但是位图也试过了，没有用。应该有其他方法，肯定也是遍历一遍就求解的。记得之前程序员面试金典中有一道题是：给定一个数组，求出数组缺少的值，好像是从0开始。如果不是从0开始就返回0。如果一直都是连续，返回连续的数最后后面一个值。之前题目的解法是：0~n的数组A,通过分析n为奇数和偶数，找到统计中最低位（二进制）1和0的个数关系，分析丢失的某数后，实际的0和1关系，将与丢失最低有效位不等的全部排除，然后进行次最低位的计算但是位运算似乎和本题无关。我是否可以将每个整数转化为二进制，然后寻找规律做。leecode解法:https://leetcode.com/PRoblems/longest-consecutive-sequence/?tab=Solutions关键：1 设定一个map，键是存储当前元素，值是包含还元素的连续序列的长度。对于当前元素n，如果其左边元素n-1也在映射中，则获取其左边元素对应的连续序列长度left，如果没有返回0同理获取其右边元素n+1对应的连续序列长度right，如果没有返回0令当前元素长度=左边相邻元素的连续序列长度+1+右边相邻元素的连续序列长度牛逼的一步：将n-left对应长度为sum加入映射，将n+right对应长度的sum加入映射，更新，否则后续无法接收到更新信息。2 哈希map如果是查找就直接用查找，不要用count,浪费性能，count一定是完全遍历一遍，find如果找到一个，就直接返回了*/class Solution {public:	int longestConsecutive(vector<int>& nums) {		if(nums.empty())		{			return 0;		}		int size = nums.size();		int left;		int right;		unordered_map<int , int> numToSequenceLength;//存储元素到包含该元素在内的连续子序列长度		int value;		int len;		int result = 0;		for(int i = 0 ; i < size ; i++)		{			value = nums.at(i);			//如果当前元素没有访问过			if(numToSequenceLength.find(value) == numToSequenceLength.end())			{				//尝试寻找包含当前元素左边元素的连续子序列长度				if(numToSequenceLength.find(value-1) != numToSequenceLength.end())				{					left = numToSequenceLength[value-1];				}				else				{					left = 0;				}				if(numToSequenceLength.find(value+1) != numToSequenceLength.end())				{					right = numToSequenceLength[value+1];				}				else				{					right = 0;				}				len = left + 1 + right;				//将当前结果压入结果集				numToSequenceLength[value] = len;				result = max(result , len);				//更新左边界元素对应的连续子序列长度				numToSequenceLength[value - left] = len;				numToSequenceLength[value + right] = len;			}		}		return result;	}};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 int size = solution.longestConsecutive(nums);		 cout << size << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}	/*	//位图做法，    int longestConsecutive(vector<int>& nums) {		if(nums.empty())		{			return 0;		}		if(1 == nums.size())		{			return 1;		}		int size = nums.size();        int maxNum = INT_MIN;		int minNum = INT_MAX;		for(int i = 0 ; i < size ; i++)		{			maxNum = max(maxNum , nums.at(i));			minNum = min(minNum , nums.at(i));		}		long long lMax = (long long) maxNum;		long long lMin = (long long) minNum;		//判断是否需要添加偏移量		long long offset = lMin * (-1);		long long realSize = lMax - lMin + 1;		//总体长度为lMax - lMin，总体偏移量为 lMin + offset = 0, offset = -lMin;		vector<int> counts( realSize , 0 );		for(int i = 0 ; i < size ; i++)		{			//必须加上偏移量			counts.at( nums.at(i) + offset)++;		}		long long maxLen = 1;		long long beg = lMin + offset;		long long end = lMin + offset;		//如果下一个元素和上一个元素不同		for(long long i = lMin + offset + 1 ; i <= lMax + offset ; i++)		{			//如果当前位置没有元素，此时子序列已经断开，计算之前的子序列长度			if( counts.at( i ) <= 0)			{				//如果当前的元素已经计算过				maxLen = max( end - beg + 1 , maxLen );				beg = end = -1;			}			//说明当前有元素是连着的			else			{				//如果是初次，还需要更新beg				if(-1 == beg)				{					beg = i;				}				end = i;			}		}		int result = (int)maxLen;		return result;	}    int longestConsecutive2(vector<int>& nums) {		if(nums.empty())		{			return 0;		}		int size = nums.size();        int maxNum = INT_MIN;		int minNum = INT_MAX;		for(int i = 0 ; i < size ; i++)		{			maxNum = max(maxNum , nums.at(i));			minNum = min(minNum , nums.at(i));		}		long long lMax = (long long) maxNum;		long long lMin = (long long) minNum;		//判断是否需要添加偏移量		long long offset = 0;		long long realSize = 0;				if(lMin < 0)		{			offset = minNum * (-1);			//最小值和最大值都小于0，则偏移量为lMin的相反数			if(lMax < 0)			{				realSize = offset;			}			else			{				realSize = offset + lMax;			}		}		//最小值和最大值都大于0，不需要偏移量，实际大小就是最大值		else		{			realSize = lMax;		}		//long long realSize = offset + lMax;		//const long long lSize = realSize;		//const int a = 100;		//初始化位图		long long a = (long long)2147483647;		long long b = a * 2;		long long c= b + 1;		const long long eleSize = 2147483647 + 2147483647 + 1;		bitset<eleSize> bits;//bitset<位数> bits(u);u是用来初始化的，可以为二进制，长整型，字符串    }	*/