【LeetCode从零单刷】Longest Consecutive Sequence
1663 ワード
タイトル:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given
Your algorithm should run in O(n) complexity.
回答;
O(n)の時間的複雑さを見ると,動的計画を用いるかどうかを推測する.そして長い間考えていた状態遷移方程式が見つからず・・・
結果としてDiscussの中はすべて容器で計算される(O(n)はDPとは限らず,容器としても考えられる).このシーケンスには重複要素がある可能性があるため、set関連コンテナを使用すると、コンテナに重複要素が含まれないようにできます.
しかし、set/mapは赤黒ツリーに基づいて実現されるため、検索効率はO(log n)レベルである.したがって、hashmapベースのunordered_を使用することができます.setコンテナ、検索効率は定数レベルです.
アクセスした要素を保存するコンテナを設定します.各要素は、++および--部分を巡回します.
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)の時間的複雑さを見ると,動的計画を用いるかどうかを推測する.そして長い間考えていた状態遷移方程式が見つからず・・・
結果としてDiscussの中はすべて容器で計算される(O(n)はDPとは限らず,容器としても考えられる).このシーケンスには重複要素がある可能性があるため、set関連コンテナを使用すると、コンテナに重複要素が含まれないようにできます.
しかし、set/mapは赤黒ツリーに基づいて実現されるため、検索効率はO(log n)レベルである.したがって、hashmapベースのunordered_を使用することができます.setコンテナ、検索効率は定数レベルです.
アクセスした要素を保存するコンテナを設定します.各要素は、++および--部分を巡回します.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> visited;
unordered_set<int> all(nums.begin(), nums.end());
int max = 0;
int count, tmp;
int size = nums.size();
for(int i=0; i<size; i++) {
if (visited.find(nums[i]) != visited.end()) continue;
visited.insert(nums[i]);
count = 1;
tmp = nums[i];
while(all.find(tmp - 1) != all.end()) {
count++;
tmp--;
visited.insert(tmp);
}
tmp = nums[i];
while(all.find(tmp + 1) != all.end()) {
count++;
tmp++;
visited.insert(tmp);
}
if (count > max) max = count;
}
return max;
}
};