Description:
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Your algorithm should run in O(n) complexity.
Example:
For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Link:
https://leetcode.com/problems/longest-consecutive-sequence/description/
解题方法:
这道题要求在O(n)时间解出,所以不能对数组进行排序。
解题思路参考:https://blog.csdn.net/fightforyourdream/article/details/15024861
O(n)解法为:把所有数都存到hashset中去,每遇到一个数,就把比它大的和比它小的连续的数都找一遍,在找的过程中把这些数都从hashset中删掉,防止重复查找。
比如例子:100, 4, 200, 1, 3, 2都加入hashset
当找100时,把100删掉,此时hashset: 4, 200, 1, 3, 2
.
.
.
当找到4时,找完以后的hashset: 200 (100在第一轮被删掉,1 2 3都在找比4小的连续数过程中都被删掉)
Time Complexity:
O(N)
完整代码:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> hash;
for(int i: nums)
hash.insert(i);
int result = 0;
for(int i: nums) {
int cnt = 1;
hash.erase(i);
int temp = i - 1;
//find less
while(hash.find(temp) != hash.end()) {
cnt++;
hash.erase(temp--);
}
temp = i + 1;
while(hash.find(temp) != hash.end()) {
cnt++;
hash.erase(temp++);
}
result = max(result, cnt);
}
return result;
}
网友评论