首页 > 代码库 > LeetCode "Longest Consecutive Sequence"
LeetCode "Longest Consecutive Sequence"
Comparison-based sorting takes O(nlgn), so hashset is a good idea. After keeping records of all numbers in the hashset, you start checking each number. If it is isolated (no n-1 nor n+1) that number will be removed from hashset; If not isolated, we do a BFS scanning. Since each number is only checked once, it is O(n) with 2 passes.
class Solution {public: int longestConsecutive(vector<int> &num) { unordered_set<int> rec; for (int i : num ) if(rec.find(i) == rec.end()) rec.insert(i); int cnt = 1, currcnt = 0; while(!rec.empty()) { int i = *rec.begin(); if( (rec.find(i - 1) == rec.end()) && (rec.find(i + 1) == rec.end()) ) { rec.erase(i); continue; } queue<int> q; q.push(i); while(!q.empty()) { int n = q.front(); currcnt ++; q.pop(); rec.erase(n); if(rec.find(n - 1) != rec.end()) q.push(n - 1); if(rec.find(n + 1) != rec.end()) q.push(n + 1); } cnt = std::max(currcnt, cnt); currcnt = 0; } return cnt; }};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。