问题:
[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; } };
|
方法二:聚类操作
·待补充