Longest Consecutive Sequence

最新推荐文章于 2025-03-19 23:17:40 发布

FightForProgrammer

最新推荐文章于 2025-03-19 23:17:40 发布

阅读量640

点赞数

分类专栏： LeetCode 文章标签： algorithm hashtable 遍历 Longest Consecutive

本文链接：https://blog.csdn.net/FightForProgrammer/article/details/41092375

版权

LeetCode 专栏收录该内容

44 篇文章

订阅专栏

本文介绍了一种在O(n)复杂度下查找给定无序整数数组中最长连续序列的算法。通过利用哈希表以空间换取时间，实现快速查找连续元素并更新最长序列长度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

LeetCode Longest Consecutive Sequenc

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）中解决，因此普通的先排序再进行找的方法不行，因为最快的快排都要O(nlog(n))时间

因此肯定要使用其他的办法，要加强时间的缩减，因此可以利用哈希算法：以空间换取时间！

思路：由于需要查找最长连续的序列，因此可以考虑遍历数组，对于数组中的任意元素，查找它前面和后面的连续元素，每查找到就让计数器增一，最终记录最大的数目就是最长的序列。要注意的是每次查找的过程都可以删除找过的元素，因为最大长度始终记录在计数器中。

int longestConsecutive(vector<int> &num)
{
	int len = num.size();
	map<int, int> hashTable;
	for(int i=0; i<len; ++i)
	{
		hashTable.insert(pair<int, int>(num[i], i));
	}

	int res = 0, count = 0;
	//遍历数组中的每个元素，取出每个元素进行查找
	for(int i=0; i<len; i++)
	{
		//取出数组中第i个元素
		int number = num[i];
		map<int, int>::iterator it = hashTable.find(num[i]);
		count++;
		//如果在哈希表中找到num【i】，则找它前面和后面的元素，并统计总个数
		if(it!=hashTable.end())
		{
			while(true)
			{
				//找比num[i]大，并且连续的元素,++number,一个一个的向前找
				map<int, int>::iterator it_tmp = hashTable.find(++number);
				if(it_tmp==hashTable.end())
					break;
				count++;
				hashTable.erase(it_tmp);
			}

			number = num[i];
			while(true)
			{
				//找比num[i]小，并且连续的元素,--number,一个一个的向后找
				map<int, int>::iterator it_tmp = hashTable.find(--number);
				if(it_tmp == hashTable.end())
					break;
				count++;
				hashTable.erase(it_tmp);
			}

			if(res < count)
				res = count;			
		}
		count=0;
	}

	return res;
}