【Leetcode】128. Longest Consecutive Sequence

Description

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.

Solution

public int longestConsecutive(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        Map<Integer, Integer> map = new HashMap<>();
        int max = 1;
        for (int i = 0; i < nums.length; i++) {
            //map不会包含nums[i]
            if (map.containsKey(nums[i])) {
                continue;
            } else {
                map.put(nums[i], 1);
                if (map.containsKey(nums[i] + 1) && map.containsKey(nums[i]- 1)) {
                    //look for both sides
                    int count1 = 1;
                    while (map.containsKey(nums[i] + count1)) {
                        count1++;
                    }
                    int rightBorder = nums[i] + count1 - 1;

                    int count2 = 1;
                    while (map.containsKey(nums[i] - count2)) {
                        count2++;
                    }
                    int leftBorder = nums[i] - count2 + 1;

                    int temp = map.get(leftBorder) + map.get(rightBorder) + 1;
                    map.put(leftBorder, temp);
                    map.put(rightBorder, temp);
                    max = Math.max(max, map.get(leftBorder));
                } else if (map.containsKey(nums[i] - 1)) {
                    //look for left
                    int count3 = 1;
                    while (map.containsKey(nums[i] - count3)) {
                        count3++;
                    }
                    int leftBoard1 = nums[i] - count3 + 1;
                    int temp2 = map.get(leftBoard1) + 1;
                    map.put(leftBoard1, temp2);
                    map.put(nums[i], temp2);
                    max = Math.max(max, map.get(nums[i]));
                } else if (map.containsKey(nums[i] + 1)) {
                    //look for right
                    int count4 = 1;
                    while (map.containsKey(nums[i] + count4)) {
                        count4++;
                    }
                    int rightBorder1 = nums[i] + count4 - 1;
                    int temp3 = map.get(rightBorder1) + 1;
                    map.put(rightBorder1, temp3);
                    map.put(nums[i], temp3);
                    max = Math.max(max, map.get(nums[i]));
                }
            }
        }
        return max;
    }

Result

TLE

Analyse

这里开始没有思路，然后看了一下结题思路，自己的解法，复杂度是O(n ^ 2)，出现TLE也很正常，说明在思路和代码的转化过程中还是有一定差距。

Optimization

First

public int longestConsecutive(int[] nums) {
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums) {
            if (!map.containsKey(n)) {
                int left = map.containsKey(n - 1) ? map.get(n - 1) : 0;
                int right = map.containsKey(n + 1) ? map.get(n + 1) : 0;
                int sum = left + right + 1;
                map.put(n, sum);
                res = Math.max(res, sum);

                map.put(n - left, sum);
                map.put(n + right, sum);
            } else {
                continue;
            }
        }
        return res;
    }

Second

public int longestConsecutive(int[] nums) {
        if (nums.length <= 1) {
            return nums.length;
        }
        Set<Integer> set = new HashSet<>();
        int max = 1;
        for (int n : nums) {
            set.add(n);
        }
        for (int n : nums) {
            if (set.remove(n)) {
                int num = n;
                int sum = 1;
                while (set.remove(num - 1)) {
                    num--;
                }
                sum += n - num;

                num = n;
                while (set.remove(num + 1)) {
                    num++;
                }
                sum += num - n;
                max = Math.max(max, sum);
            }
        }
        return max;
    }

Analyse

这里用了一个思路就是，一个连续的数组的话，边界的key存储的value都是这个连续数组的长度。每次都依次进行更新。而第二个set的思路更为简单，主要还是利用set的api，熟悉remove方法的话就会很容易。这里的复杂度都是O(n)。