Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example,
Given
The longest consecutive elements sequence is
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 table。将序列中的所有数存到一个unordered_set中。对于序列里任意一个数A[i]，我们可以通过set马上能知道A[i]+1和A[i]-1是否也在序列中。如果在，继续找A[i]+2和A[i]-2，以此类推，直到将整个连续序列找到。为了避免在扫描到A[i]-1时再次重复搜索该序列，在从每次搜索的同时将搜索到的数从set中删除。直到set中为空时，所有连续序列搜索结束。
复杂度：由于每个数字只被插入set一次，并删除一次，所以算法是O(n)的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | class Solution { public: int longestConsecutive(vector<int> &num) { if(num.empty()) return 0; unordered_set<int> ht; for(int i=0; i<num.size(); i++) ht.insert(num[i]); int maxLen = 1; for(int i=0; i<num.size(); i++) { if(ht.empty()) break; int curLen = 0; int curNum = num[i]; while(ht.count(curNum)) { ht.erase(curNum); curLen++; curNum++; } curNum = num[i]-1; while(ht.count(curNum)) { ht.erase(curNum); curLen++; curNum--; } maxLen = max(maxLen, curLen); } return maxLen; } }; |
I have one solution:
ReplyDeletepublic class Solution {
public int longestConsecutive(int[] num) {
int longest = 0;
Map map = new HashMap();
for(int i = 0; i< num.length; i++){
map.put(num[i], false);
}
int l, k;
for(int i = 0;i < num.length;i++){
if(map.containsKey(num[i]-1) || map.get(num[i])) continue;
map.put(num[i], true);
l = 0; k = num[i];
while (map.containsKey(k)){
l++;
k++;
}
if(longest < l) longest = l;
}
return longest;
}
}
Other approaches can b found at http://traceformula.blogspot.com/2015/07/longest-consecutive-sequence-some.html
I have one solution:
ReplyDeletepublic class Solution {
public int longestConsecutive(int[] num) {
int longest = 0;
Map map = new HashMap();
for(int i = 0; i< num.length; i++){
map.put(num[i], false);
}
int l, k;
for(int i = 0;i < num.length;i++){
if(map.containsKey(num[i]-1) || map.get(num[i])) continue;
map.put(num[i], true);
l = 0; k = num[i];
while (map.containsKey(k)){
l++;
k++;
}
if(longest < l) longest = l;
}
return longest;
}
}
Other approaches can b found at http://traceformula.blogspot.com/2015/07/longest-consecutive-sequence-some.html
Java has a super amazing Data Structure called PriorityQueue, which is also used to build Heap in Java.
ReplyDeleteHere is one solution, which don't need to scan backwards.
public class Solution {
public int longestConsecutive(int[] nums) {
if(nums == null || nums.length == 0){
return 0;
}
PriorityQueue pq = new PriorityQueue();
for(int i=0;i<nums.length;i++){
pq.add(nums[i]);
}
int rst = 0;
while(pq.isEmpty() == false){
int number = pq.peek(), times = 0;
while(pq.contains(number)){
pq.remove(number);
number++;times++;
}
rst = Math.max(rst, times);
}
return rst;
}
}
Priority queue's push time is not O(1), your algorithm will take nlogn
Deletep.s. C++ also has priority queue
How about theses sorting algorithms in linear time, such as counting sort?
ReplyDelete