[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&&AC代碼

我首先考慮的就是先進行數組排序，然後查找，具體步驟如下： 數組排序分別考慮三種情況：（1）下一個值等於當前值+1（2）下一個值等於當前值（3）其他

AC代碼

public class Solution {
    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }

        Arrays.sort(num);

        int len, tmp, i;

        for (len = tmp = i = 0; i + 1 < num.length; i++) {
            if (num[i + 1] - num[i] == 1) {
                tmp++;
            } else if (num[i + 1] == num[i]) {
                // do nothing
            } else {
                if (tmp > len) {
                    len = tmp;
                }
                tmp = 0;
            }
        }

        if (tmp > len) {
            len = tmp;
        }

        return len + 1;
    }
}

分析

這道題目，首先采用了系統的排序函數，Arrays.sort(),不管系統函數如何優化，我們都可以認定時間復雜度是大於O(n)的，一般是O(nlogn)

思路2&&AC代碼

在要求O(n)的是復雜度，而且數組未排序的情況下，應該考慮使用HashSet，首先排除重復元素，並且查找元素的時間復雜度為O(1)

AC代碼

public class Solution {
    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }

        HashSet set = new HashSet();

        for (int i = 0; i < num.length; i++) {
            set.add(num[i]);
        }

        int res = 0;

        for (int i = 0; i < num.length; i++) {
            if (set.contains(num[i])) {
                set.remove(num[i]);

                int tmp = 1;
                int next = num[i] + 1;
                while (set.contains(next)) {
                    set.remove(next);
                    next++;
                    tmp++;
                }

                next = num[i] - 1;
                while (set.contains(next)) {
                    set.remove(next);
                    next--;
                    tmp++;
                }

                res = Math.max(tmp, res);
            }
        }

        return res;
    }
}