首页 > 代码库 > 24. Longest Consecutive Sequence
24. Longest Consecutive Sequence
Longest Consecutive Sequence
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.
两种方法:1. 利用 hash_map 结构,数组有序时查找的思想。
class Solution {public: int longestConsecutive(vector<int> &num) { if(num.size() == 0) return 0; unordered_map<int, bool> _map; for(size_t i = 0; i < num.size(); ++i) _map.insert(pair<int ,bool>(num[i], false)); int ans = 0; for(auto it = _map.begin(); it != _map.end(); ++it) { if(it->second) continue; // visited int len = 1; int v1 = it->first-1; while(_map.count(v1)) { _map[v1--] = true; len++; } int v2 = it->first+1; while(_map.count(v2)) { _map[v2++] = true; len++; } if(len > ans) ans = len; } return ans; }};
2. 动态的构造有向线段(矢量)(两端为线段始末位置)。若当前点可增加有向线段长度,拓展线段。
class Solution {public: int longestConsecutive(vector<int> &num) { int answer = 0; unordered_map<int ,int>_map; int low, high; for(int i = 0; i < num.size(); ++i) { if(_map.count(num[i])) continue; // must be used. _map[num[i]] = num[i]; low = high = num[i]; if(_map.count(num[i]-1)) low = _map[num[i]-1]; if(_map.count(num[i]+1)) high = _map[num[i]+1]; answer = max(answer, high - low + 1); if(low == high) continue;// not in a line _map[low] = high; _map[high] = low; } return answer; }};
24. Longest Consecutive Sequence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。