Question

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

Your algorithm should run in O(n) complexity.

Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

Thinking:

  • Method1:通过并查集，但是效率是O(N + nlgn).使用的是quick-union。
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for(int n : nums){
            if(!map.containsKey(n)){
                map.put(n, map.containsKey(n - 1) ? n - 1 : n);
                if(map.containsKey(n + 1))
                    map.put(n + 1, n);
            }
        }
        int result = 0;
        int count = 1;
        for(Integer i : map.keySet()){
            int num = i;
            while(map.get(num) != num){
                num = map.get(num);
                count++;
            }
            result = Math.max(result, count);
            count = 1;
        }
        return result;
    }
}
  • Method 2: 使用HashSet
class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int len = nums.length;
        Set<Integer> pool = new HashSet<>();
        for(int n : nums)
            pool.add(n);
        int max = 0;
        for(Integer i : pool){
            if(!pool.contains(i - 1)){
                int count = 1;
                while(pool.contains(++i)){
                    count++;
                }
                max = Math.max(count, max);
            }
        }
        return max;
    }
}

二刷

其实用Set就可以解决问题，最重要的是，要判断前面的那一位数字并不存在，减少了很多无谓的判断。

class Solution {
    public int longestConsecutive(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        Set<Integer> set = new HashSet<>();
        for(int n : nums) set.add(n);
        int result = 0;
        for(int i = 0; i < nums.length; i++){
            int res = 1;
            if(!set.contains(nums[i] - 1)){
                while(set.contains(++nums[i])){
                    res++;
                }
            }
            result = Math.max(res, result);
        }
        return result;
    }
}