寻找未排序数组的最长连续序列

问题：

[100, 4, 200, 1, 3, 2] 最长连续序列：[1, 2, 3, 4]。
复杂度：O(n)

方法一

先排序，复杂度O(nlogn)。
要求O(n)，用哈希表。用一个哈希表记录每个元素是否使用，对每个元素，已该元素为中心，向左右扩张，直到不连续为止，记录下最长的长度。
[unordered_map](http://www.cplusplus.com/reference/unordered_map/unordered_map/)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
	int longestConsecutive(const vector<int> &nums) {
		unordered_map<int, bool> used;
		for (auto i : nums) used[i] = false;

		int longest = 0;

		for (auto i : nums) {
			if (nums[i]) continue;

			int length = 1;
			used[i] = true;

			for (int j = i + 1; used.find(j) != used.end(); ++j) {
				used[j] = true;
				++length;
			}
			for (int j = i - 1; used.find(j) != used.end(); --j) {
				used[j] = true;
				++length;
			}

			longest = max(longest, length);
		}

		return longest;
	}
};

方法二：聚类操作

·待补充

Comments

2016-03-08
▲