[LeetCode]Longest Consecutive Sequence.cpp

实际上interval merge的问题，很容易就可以想到要用hashmap来记录每个interval的起点和终点。对于一个数i，我们每次需要去map中找以i - 1结尾的interval和i + 1开头的interval然后做相应的更新，同时还需要去重。那代表我们需要两个hashmap来分别记录头尾，一个set用来去重。但是我们真的需要这么用这么多数据结构吗？事实上如果稍微仔细地思考一下，就会发现一个hash map可以完美满足我们的所有需求。我们用map记录以下的东西

• 如果i为某个interval的起点或者终点，那么map[i]记录interval的长度
• 否则，map[i]的值无关紧要，map对于这些i的作用是去重，已经考虑过的i就不需要再考虑了

那么很显然，这样的一个map完全就够用了。对于新插入的i，有以下几种情况：

• i已经在map里，跳过
• i -1和i + 1都不在map里，i自己形成了一个interval，map[i] = 1;
• i - 1和i + 1只有其中一个在map中，那么相应的我们插入i可以让已经在map中的某个interval向左或者向右扩展，假设扩展前长度为len，map[i] = len + 1，map[i - len] = len + 1
• i - 1和i + 1都在map中，那么我们可以讲原本在map中的interval merge成一个更长的interval，假设原本在左边的interval长len1，右边的长len2，那么map[i - len] = len1 + len2 + 1, map[i + len] = len1 + len2 + 1, map[i]的值随意

我们同时记录最长的interval，那么最后的结果就是我们要的Longest Consecutive Sequence。时间负责度O(n)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int longestConsecutive(vector<int>& nums) {
	int len = 0, maxLen = 0;
	//we just need a single map to solve this problem
	unordered_map<int, int> map;
	for(auto& i : nums)
	{
	if(map.find(i) != map.end())continue;
	int leftLen = map.find(i - 1) != map.end()? map[i - 1]: 0;
	int rightLen = map.find(i + 1) != map.end()? map[i + 1]: 0;
	maxLen = max(maxLen, leftLen + rightLen + 1);
	if(leftLen)
	map[i - leftLen] = leftLen + rightLen + 1;
	if(rightLen)
	map[i + rightLen] = leftLen + rightLen + 1;
	map[i] = leftLen + rightLen + 1;
	}
	return maxLen;
	}
	};

view raw Longest Consecutive Sequence.cpp hosted with ❤ by GitHub