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.

思路:

既然要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;
    }
};

5 comments:

  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

    ReplyDelete
  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

    ReplyDelete
  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++){
    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;
    }
    }

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

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

    ReplyDelete