Longest Consecutive SequenceFeb 14
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)的限制。
因此用hash来搞。
class Solution { public: int longestConsecutive(vector<int> &num) { unordered_map<int, int> hash; vector<bool> flag(num.size(), false); for (int i = 0; i < num.size(); ++i) { hash[num[i]] = i; } int maxlen = 1; int less = 0, more = 0; for (int i = 0; i < num.size(); ++i) { if (flag[i]) continue; int tmp = num[i]; auto it = hash.find(--tmp); less = 0; while (it != hash.end()) { ++less; flag[it->second] = true; it = hash.find(--tmp); } tmp = num[i]; auto it2 = hash.find(++tmp); more = 0; while (it2 != hash.end()) { ++more; flag[it2->second] = true; it2 = hash.find(++tmp); } tmp = less + more + 1; maxlen = maxlen > tmp ? maxlen : tmp; } return maxlen; } };
class Solution { public: int longestConsecutive(vector<int> &num) { unordered_map<int, bool> m; int len = num.size(); for (int i = 0; i < len; i++) { m[num[i]] = false; } int res = 0; for (int i = 0; i < len; i++) { if (m[num[i]]) continue; int low = num[i], high = num[i]; while (m.count(low) != 0) m[low] = true, low--; while (m.count(high) != 0) m[high] = true, high++; int t = high - low - 1; if (t > res) res = t; } return res; } };
相关推荐
LeetCode Longest Common Prefix解决方案
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000. Java AC 版本
Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...
Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next Permutation 公式 13 Permutation Sequence 公式 14 Valid ...
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
刷LeetCode刷LeetCode刷LeetCode刷LeetCode刷LeetCode
leetcode 分类 Leetcode代码题解 随缘刷题,选择性更新题解 LeetCode 94 144 145 ...longest-consecutive-sequence 最长连续序列: Leetcode 155 Min Stack 最小栈: LeetCode 773 滑动谜题: ......
答案LeetCode-Longest_Substring_Without_Repeating_Characters 这是LeetCode上“最长子串无重复字符”问题的解决方案。 问题描述:给定一个字符串,求没有重复字符的最长子串的长度。 示例 1:输入:“abcabcbb” ...
大佬的leetcode刷题笔记(c++版本)
vs code LeetCode 插件
leetcode中文版
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101.zip
LeetCode 101_C++_算法_leetcode_leetcode101_leetcode101_源码.zip
100个leetCode详细解答
java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...Longest Substring Without Repeating Characters LeetCode 13 Roman to Integer LeetCode 6 Zi
LeetCode 刷题汇总1
LeetCode 选讲1
leetcode正方体收藏TakeUforward-SDE_180 要了解整个列表和其他内容,如项目、简历、如何进行面试……观看整个视频: 在以下位置找到展示位置系列: ...Consecutive Sequence Longest Subarray with 0 sum 给定
terminal-leetcode, 终端Leetcode是基于终端的Leetcode网站查看器 终端 leetcode终端leetcode是基于终端的leetcode网站查看器。本项目是由 RTV 激发的。 我最近正在学习本地化的反应,以实践我的新知识,并根据这个...
longest-consecutive-sequence max-area-of-island next-greater-element-ii serialize-and-deserialize-binary-tree subarray-sum-equals-k binary-tree-preorder-traversal n-queens-ii populating-next-right-...