[LeetCode]Longest Consecutive Sequence, 解题报告 - c++编程基础

题目

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; } }