【LeetCode】19 最长连续序列

题目

给定一个未排序的整数数组,找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

方法1 排序 思路

想法

如果我们可以将数组中的数字升序迭代,找连续数字会变得十分容易。为了将数组变得有序,我们将数组进行排序。

算法

在我们开始算法之前,首先检查输入的数组是否为空数组,如果是,函数直接返回 0 。对于其他情况,我们将 nums 数组排序,并考虑除了第一个数字以外的每个数字与它前一个数字的关系。如果当前数字和前一个数字相等,那么我们当前的序列既不会增长也不会中断,我们只需要继续考虑下一个数字。如果不相等,我们必须要检查当前数字是否能延长答案序列(也就是 nums[i] == nums[i-1] + 1)。如果可以增长,那么我们将当前数字添加到当前序列并继续。否则,当前序列被中断,我们记录当前序列的长度并将序列长度重置为 1 。由于 nums 中的最后一个数字也可能是答案序列的一部分,所以我们将当前序列的长度和记录下来的最长序列的长度的较大值返回。

image.png

如上是一个例子。在做线性查找所有连续序列之前,先将数组进行了排序。
标红的是最长连续序列。

方法1 排序 代码

package com.janeroad;


import java.util.Arrays;

public class test7 {
public int longestConsecutive(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    Arrays.sort(nums);
    int longestStreak = 1;
    int currentStreak = 1;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] != nums[i-1]) {
            if (nums[i] == nums[i-1]+1) {
                currentStreak += 1;
            }
            else {
                longestStreak = Math.max(longestStreak, currentStreak);
                currentStreak = 1;
            }
        }
    }
    return Math.max(longestStreak, currentStreak);
}
public static void main(String[] args) {
    int []num={2,4,3,-1,7,6,19,100};
    test7 test7=new test7();
    System.out.println(test7.longestConsecutive(num));
}
}

方法2 哈希表和线性空间的构造 思路

想法

其实我们一开始的暴力解法的思路是正确的,但是需要进行一些优化,才能达到 O(n) 的时间复杂度。

算法

这个优化算法与暴力算法仅有两处不同:这些数字用一个 HashSet 保存(或者用 Python 里的 Set),实现 O(1)时间的查询,同时,我们只对 当前数字 - 1 不在哈希表里的数字,作为连续序列的第一个数字去找对应的最长序列,这是因为其他数字一定已经出现在了某个序列里。

方法2 哈希表和线性空间的构造 代码

class Solution {
public int longestConsecutive(int[] nums) {
    Set<Integer> num_set = new HashSet<Integer>();
    for (int num : nums) {
        num_set.add(num);
    }

    int longestStreak = 0;

    for (int num : num_set) {
        if (!num_set.contains(num-1)) {
            int currentNum = num;
            int currentStreak = 1;

            while (num_set.contains(currentNum+1)) {
                currentNum += 1;
                currentStreak += 1;
            }

            longestStreak = Math.max(longestStreak, currentStreak);
        }
    }

    return longestStreak;
}
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×