Tuesday, November 25, 2014

[LeetCode] 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 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 &num) { if(num.empty()) return 0; unordered_set ht; for(int i=0; i

1. I have one solution:
public 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

2. I have one solution:
public 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

3. Java has a super amazing Data Structure called PriorityQueue, which is also used to build Heap in Java.
Here 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++){
}

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;
}
}

1. Priority queue's push time is not O(1), your algorithm will take nlogn
p.s. C++ also has priority queue

4. How about theses sorting algorithms in linear time, such as counting sort?