首页 > 代码库 > [LeetCode] Longest Consecutive Sequence 求解

[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(1)时间查找该数字是否存在于数组当中

    - 数字有可能重复,所以其实哈希集合就够了,典型的空间换时间
  • (预处理)一个表征是否使用的used表,用于o(1)时间查找该数字是否已经被包含在另外一个序列当中

    - 注意数字有可能是负数,所以直接用数组不好
  • 轮询数组,遇到一个数字,查找其左,右的最长连续序列长度,并记录与已知最大长度相比较

public class Solution {
    public int longestConsecutive(int[] num) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        for (int i = 0; i < num.length; i++) {
            map.put(num[i], i);
        }

        Map<Integer, Boolean> used = new HashMap<Integer, Boolean>();
        for (int i : num) {
            used.put(i, false);
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < num.length; i++) {
            if (!used.get(num[i])) {
                used.put(num[i], true);

                int k = num[i];

                int leftLength = findLength(k, map, "left");
                int rightLength = findLength(k, map, "right");

                // mark used
                for (int j = 0; j < leftLength; j++) {
                    used.put(k - j - 1, true);
                }
                for (int j = 0; j < rightLength; j++) {
                    used.put(k + j + 1, true);
                }

                int total = leftLength + rightLength + 1;
                if (total > max) {
                    max = total;
                }

            }
        }
        return max;
    }

    private int findLength(int k, Map<Integer, Integer> map, String direction) {
        if ("left".equals(direction)) {
            int l = k - 1;
            while (map.containsKey(l)) {
                l -= 1;
            }
            return k - l - 1;
        } else {
            int l = k + 1;
            while (map.containsKey(l)) {
                l += 1;
            }
            return l - k - 1;
        }
    }
}

[LeetCode] Longest Consecutive Sequence 求解