描述 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.
分析 如果允許 O(n log n) 的復雜度，那么可以先排序，可是本題要求 O(n)。 由于序列里的元素是無序的，又要求 O(n)，首先要想到用哈希表。 用一個哈希表 unordered_map
class Solution {public: int longestConsecutive(vector<int>& nums) { unordered_map<int, bool> used; for (auto i : nums) used[i] = false; int longest = 0; for (auto i : nums) { if (used[i] == true) 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 = (length < longest) ? longest : length; } return longest; }};新聞熱點
疑難解答
