LeetCode-128-最长连续序列

最长连续序列

题目描述:给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-consecutive-sequence/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:哈希表

因为哈希查找比较快,所以用哈希表来辅助计算,具体处理过程如下:

  • 首先,用HashSet将原数组中的数字去重得到numsSet;
  • 然后,遍历numsSet中的所有数字,用currentConsecutiveNums记录以当前数字为起点,连续的数且在numsSet中的最长序列长度,通过哈希查找在numsSet中查找这些连续的数字,最后得到当前数字对应的最长连续序列长度;
  • 如果当前数字对应的最长连续序列长度比已知的最长连续序列longestConsecutiveNums大,则更新最长连续序列longestConsecutiveNums的值。

最后,返回longestConsecutiveNums即为连续的最长序列的长度。

import java.util.HashSet;
import java.util.Set;

public class LeetCode_128 {
    /**
     * 哈希表
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        // 去重后的数
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num);
        }

        // 记录最长的连续序列
        int longestConsecutiveNums = 0;

        for (Integer num : numsSet) {
            if (!numsSet.contains(num - 1)) {
                // 当前的数
                int currentNum = num;
                // 当前的数连续的序列的长度,初始值为1
                int currentConsecutiveNums = 1;

                // 获取以当前数字为起点,连续的数且在numsSet中的长度
                while (numsSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentConsecutiveNums += 1;
                }

                // 如果当前的最大连续长度大于最大的的连续序列,则更新最大的连续序列
                longestConsecutiveNums = Math.max(longestConsecutiveNums, currentConsecutiveNums);
            }
        }
        return longestConsecutiveNums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{100, 4, 200, 1, 3, 2};
        // 测试用例,期望输出: 4
        System.out.println(longestConsecutive(nums));
    }
}

【每日寄语】 第一个青春是上帝给的;第二个的青春是靠自己努力的。

上一篇:2021209 LeetCode刷题 自除数(难度 :简单)


下一篇:128. 最长连续序列