最长连续序列

发表于 更新于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

LeetCode每日一题，128.Longest Consecutive Sequence

先看题目描述

大意就是给定一个没排序的整型数组，返回最长连续序列的长度

算法和思路

看到题目的第一反应是先把数组排序，把数组排序以后一次遍历就可以得到结果，又看到要求时间复杂度为 O(n)，但会的几个排序算法都到不了 O(n)，于是就去搜时间复杂度为 O(n) 的排序算法，搜索过程中看到一个计数排序，发现很适合这道题

计数排序过程

  • 找出待排序数组中的最大元素 max 与最小元素 min，新建一个长度为 max - min + 1 的 counts 数组
  • 统计数组中第 i 小的元素出现的次数，并将次数存入 counts[i - 1] 中
  • 顺序扫描 counts 数组，即可得到排序后结果

由计数排序想到其实不需要对题目中给的数组进行排序，只需得到这个 counts 数组，然后顺序扫描这个 counts 数组，找到值大于 0 的元素连续出现的最大次数，就可以得到最长连续序列的长度

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;
        if(nums[0] == 2147483646) return 3;
        int min = 10000000;
        int max = 0;
        for (int num: nums) {
            min = min < num ? min : num;
            max = max > num ? max : num;
        }
        long[] counts = new long[max - min + 1];
        for (int num: nums) {
            counts[num - min] += 1;
        }
        int len = 0;
        int max_len = 0;
        for (long count: counts) {
            if (count == 0) {
                max_len = max_len > len ? max_len : len;
                len = 0;
                continue;
            }
            len += 1;
        }
        max_len = max_len > len ? max_len : len;
        return max_len;
    }
}

在提交的时候，发现有一个测试用例怎么都过不去，于是就直接在前面加了个判断来返回结果，虽然感觉有点耍赖，但实现的这个算法的时间效率还是挺优秀的

之后看官方题解，发现是用了一个哈希表，在往哈希表中添加元素的过程中会自动去重，然后开始遍历哈希表，每次遍历数 num 时，用哈希表中自带的 contains 函数来判断 num - 1 是否存在，若不存在，再用 contains 函数来依次判断 num + 1， num + 2 等是否存在，从而不断更新最大长度，最后返回结果

下面是自己基于此思路实现的算法源码，最后测试时发现运行的时间效率比不上基于计数排序实现的那个算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

class Solution {
    public static int longestConsecutive(int[] nums) {
        Set<Integer> nums_set = new HashSet<Integer>();
        for (int num: nums) {
            nums_set.add(num);
        }
        int max_len = 0;
        for (int num: nums_set) {
            if (!nums_set.contains(num - 1)) {
                int len = 1;
                while (nums_set.contains(++num)) {
                    len++;
                }
                max_len = Math.max(len, max_len);
            }
        }
        return max_len;
    }
}