#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.分析:題目給定一個未排序的數(shù)組，需要找出最大連續(xù)序列，返回它的長度。時間復(fù)雜度必須為O(n)。如果允許排序，那么閑排序，然后從初始部分向后遍歷，然后找到最大連續(xù)元素長度。如果用統(tǒng)計排序，遍歷一遍元素，把元素i放在對應(yīng)的位置上。遍歷完了之后，凡是A[i] > 0，則表示元素i存在，初始時，設(shè)置最大連續(xù)子序列長度為0，每當(dāng)發(fā)現(xiàn)如果下一個元素為A{i]為0，則統(tǒng)計之前的最大連續(xù)子序列長度，如果大于最大連續(xù)子序列長度就更新最大連續(xù)子序列的值。如果統(tǒng)計排序可以用的話，那其實(shí)直接用位圖來做也是可以的。由于vector存入100萬就會崩潰，必定不能開辟這么大的數(shù)據(jù)。但是這樣的會提前開辟需要知道里面的最大值，直接先遍歷一遍，得到最大值，然后用位圖。而且實(shí)際上應(yīng)該不允許有負(fù)數(shù)的。否則位圖沒辦法表示，還得獲取最小值。如果最小值小于0，還得為位圖增加偏移量?？隙ㄟ€需要添加偏移量后，實(shí)際長度會溢出，最好用long long實(shí)在不行直接初始化長度為: INT_MAX + INT_MAX + 1;反正整形只有這么多輸入:6(數(shù)組元素個數(shù))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]果然，似乎直接統(tǒng)計排序沒有用，但是位圖也試過了，沒有用。應(yīng)該有其他方法，肯定也是遍歷一遍就求解的。記得之前程序員面試金典中有一道題是：給定一個數(shù)組，求出數(shù)組缺少的值，好像是從0開始。如果不是從0開始就返回0。如果一直都是連續(xù)，返回連續(xù)的數(shù)最后后面一個值。之前題目的解法是：0~n的數(shù)組A,通過分析n為奇數(shù)和偶數(shù)，找到統(tǒng)計中最低位（二進(jìn)制）1和0的個數(shù)關(guān)系，分析丟失的某數(shù)后，實(shí)際的0和1關(guān)系，將與丟失最低有效位不等的全部排除，然后進(jìn)行次最低位的計算但是位運(yùn)算似乎和本題無關(guān)。我是否可以將每個整數(shù)轉(zhuǎn)化為二進(jìn)制，然后尋找規(guī)律做。leecode解法:https://leetcode.com/PRoblems/longest-consecutive-sequence/?tab=Solutions關(guān)鍵：1 設(shè)定一個map，鍵是存儲當(dāng)前元素，值是包含還元素的連續(xù)序列的長度。對于當(dāng)前元素n，如果其左邊元素n-1也在映射中，則獲取其左邊元素對應(yīng)的連續(xù)序列長度left，如果沒有返回0同理獲取其右邊元素n+1對應(yīng)的連續(xù)序列長度right，如果沒有返回0令當(dāng)前元素長度=左邊相鄰元素的連續(xù)序列長度+1+右邊相鄰元素的連續(xù)序列長度牛逼的一步：將n-left對應(yīng)長度為sum加入映射，將n+right對應(yīng)長度的sum加入映射，更新，否則后續(xù)無法接收到更新信息。2 哈希map如果是查找就直接用查找，不要用count,浪費(fèi)性能，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;//存儲元素到包含該元素在內(nèi)的連續(xù)子序列長度		int value;		int len;		int result = 0;		for(int i = 0 ; i < size ; i++)		{			value = nums.at(i);			//如果當(dāng)前元素沒有訪問過			if(numToSequenceLength.find(value) == numToSequenceLength.end())			{				//嘗試尋找包含當(dāng)前元素左邊元素的連續(xù)子序列長度				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;				//將當(dāng)前結(jié)果壓入結(jié)果集				numToSequenceLength[value] = len;				result = max(result , len);				//更新左邊界元素對應(yīng)的連續(xù)子序列長度				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++)		{			//如果當(dāng)前位置沒有元素，此時子序列已經(jīng)斷開，計算之前的子序列長度			if( counts.at( i ) <= 0)			{				//如果當(dāng)前的元素已經(jīng)計算過				maxLen = max( end - beg + 1 , maxLen );				beg = end = -1;			}			//說明當(dāng)前有元素是連著的			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的相反數(shù)			if(lMax < 0)			{				realSize = offset;			}			else			{				realSize = offset + lMax;			}		}		//最小值和最大值都大于0，不需要偏移量，實(shí)際大小就是最大值		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<位數(shù)> bits(u);u是用來初始化的，可以為二進(jìn)制，長整型，字符串    }	*/