leetcode 128. Longest Consecutive Sequence

题目概述

解题思路

这道题一种显而易见的O(n log n)时间复杂度的解法就是：先对整个数组进行排序，然后从头到尾遍历一遍，记录最长的连续数组。不过这题归属于hard类型，显然应该有O(n)时间复杂度的解法。

题目要求我们找到最长的连续子数组的长度，时间复杂度还要是O(n)，就是说我们不能对数组排序，不排序的话还需要动态地更新一个数组的长度，就是说我们需要知道当前一个数组的最左、最右的数。我们考虑维护一个哈希表，首先它要能记录当前的所有数组的最左和最右的数（value值大概就是长度了，或者最左+最右）；接下来考虑key值，key值直接取元素的值即可。

接下来考虑如何动态地更新哈希表。

假设哈希表H的存储格式形如：{a : a 元素所在数组的长度}

假设新增元素A[i]，在进入表H时，首先判断H中是否有A[i]：

• 如果已有，则不管它；
• 如果没有，首先要将其插入，因为不知道它长度是多少，只知道至少是1，所以插入{A[i] : 1}。
  • 接下来，去找H中是否存在A[i] - 1。如果存在，说明我们要把一个结尾元素是 A[i] - 1的数组更新一下，而这个数组的头元素也需要更新，因为有可能未来插入的新元素位于该数组头元素前一个位置。
    • 首先，将A[i]所在数组的长度更新为H[A[i] - 1] + H[A[i]]；
    • 然后，将头元素A[i] - H[A[i] - 1]的所在数组长度也更新为H[A[i] - 1] + H[A[i]]。
  • 接下来，去H中找是否存在A[i] + 1。如果存在，说明我们要把一个开头元素是A[i] + 1的数组更新一下，而这个数组的尾元素也需要更新。
    • 首先，将A[i]所在数组的长度更新为H[A[i] + 1] + H[A[i]];
    • 然后，将尾元素A[i] + H[A[i] + 1]的所在数组长度也更新为H[A[i] + 1] + H[A[i]]。

接下来，只需要维护一个数，用来比较每次更新之后的长度是否是最大的。

解法性能

O(n)时间复杂度：

O(n log n)时间复杂度：

示例代码

O(n)时间复杂度：

class Solution {
public:

	int longestConsecutive(vector<int>& nums)
	{
		unordered_map<int, int> hashs;
		int res = 1, len = nums.size(), left, right, temp_len;
        if(!len)
            return 0;            
		for (int i = 0; i < len; ++i)
		{
			if (hashs.find(nums[i]) == hashs.end())
			{
				hashs.insert(pair<int, int> {nums[i], 1});
				if (hashs.find(nums[i] - 1) != hashs.end())
				{
					left = nums[i] - hashs[nums[i] - 1];
					right = nums[i] + hashs[nums[i]] - 1;
					temp_len = right - left + 1;
					hashs[left] = temp_len;
					hashs[right] = temp_len;
					res = max(res, temp_len);
				}

				if (hashs.find(nums[i] + 1) != hashs.end())
				{
					left = nums[i] - hashs[nums[i]] + 1;
					right = nums[i] + hashs[nums[i] + 1];
					temp_len = right - left + 1;
					hashs[left] = temp_len;
					hashs[right] = temp_len;
					res = max(res, temp_len);
				}
			}
		}

		return res;
	}
};

O(n log n)时间复杂度：

class Solution {
public:
	int longestConsecutive(vector<int>& nums)
	{
		if (nums.size() == 0)
			return 0;
		int res = 1, temp_res = 1;
		sort(nums.begin(), nums.end());

		for (int i = 0; i < nums.size(); ++i)
			cout << nums[i] << ' ';
		cout << endl;

		for (int i = 0, delta; i < nums.size() - 1; ++i)
		{
			delta = nums[i + 1] - nums[i];
			if (delta == 1)
				temp_res++;
			else if(delta > 1)
			{
				res = max(res, temp_res);
				temp_res = 1;
			}
		}
		res = max(res, temp_res);

		return res;
	}
};