Problem:
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.
Idea:
Hashtable / Hashset
Time complexity: O(n)
Space complexity: O(n)
Solution 1: C++ / online
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_map<int, int> h; int ans = 0; for (int num : nums) { if (h.count(num)) continue; auto it_l = h.find(num - 1); auto it_r = h.find(num + 1); int l = it_l != h.end() ? it_l->second : 0; int r = it_r != h.end() ? it_r->second : 0; int t = l + r + 1; h[num] = h[num - l] = h[num + r] = t; ans = max(ans, t); } return ans; } }; |
Solution 2: C++ / offline
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution { public: int longestConsecutive(vector<int>& nums) { unordered_set<int> h(nums.begin(), nums.end()); int ans = 0; for (int num : nums) if (!h.count(num - 1)) { int l = 0; while (h.count(num++)) ++l; ans = max(ans, l); } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment