128. Longest Consecutive Sequence

Leetcode 问题: 128. Longest Consecutive Sequence
Categories:
Tags:

题目

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

传入一个整数阵列 nums，取得最长的连续整数长度

Example

Input: nums = [100,4,200,1,3,2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.
整数阵列 nums 100 4 200 1 3 2
连续整数 4 1 3 2 
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

演算法

1. 建立数字阵列的 Set，只取唯一值

使用 Set 确定每个数字是否有出现，不纪录重複出现的数字

2. 找到每个连续整数的起点

要计算 连续整数 的长度，必须从头开始计算，所以必须要找到每个 连续整数 的起点在哪个位置

连续整数 的起点代表他是 第 1 个 数字，所以表示 前面没有任何数字比他小

所以可以找 每个数字 - 1 确认是否存在这个数字

  • 不存在：这个数是 连续整数 的起点 第 1 个 数字
  • 不存在：这个数不是 连续整数 的起点数字

3. 寻找所有连续整数长度

找到 连续整数 的起点数字后，计算这个 连续整数 的长度

然后比较「最长连续整数长度」与「目前整数为起点，连续整数的长度」，取最长的那一个

答案

JavaScript

function longestConsecutive(numsList) {
    // 建立数字阵列的 Set，只取唯一值
    var NumsListSet = new Set(numsList);
    // 设定最长连续整数长度，预设是 0
    var longestConsecutiveNumberLength = 0;
    NumsListSet.forEach(function (currentNumber) {
        // 如果有前一个数字，前一个数字的值是
        var previousNumber = currentNumber - 1;
        if (!NumsListSet.has(previousNumber)) {
            // 如果没有前一个数字，表示这个是「连续整数」的第 1 个整数
            // 计算以目前整数为起点，连续整数的长度是多少
            var currentNumberConsecutiveNumberLength = 0;
            while (NumsListSet.has(currentNumber + currentNumberConsecutiveNumberLength)) {
                // 从头开始计算连续的整数数量，直到找不到连续的整数
                currentNumberConsecutiveNumberLength++;
            }
            // 比较「最长连续整数长度」与「目前整数为起点，连续整数的长度」，取最长的那一个
            longestConsecutiveNumberLength = Math.max(longestConsecutiveNumberLength, currentNumberConsecutiveNumberLength);
        }
    });
    return longestConsecutiveNumberLength;
}

TypeScript

function longestConsecutive(numsList: number[]): number {
    // 建立数字阵列的 Set，只取唯一值
    const NumsListSet = new Set(numsList);

    // 设定最长连续整数长度，预设是 0
    let longestConsecutiveNumberLength = 0;

    NumsListSet.forEach((currentNumber) => {
        // 如果有前一个数字，前一个数字的值是
        let previousNumber = currentNumber - 1;
        if (!NumsListSet.has(previousNumber)) {
            // 如果没有前一个数字，表示这个是「连续整数」的第 1 个整数
            // 计算以目前整数为起点，连续整数的长度是多少
            let currentNumberConsecutiveNumberLength = 0;
            while (NumsListSet.has(currentNumber + currentNumberConsecutiveNumberLength)) {
                // 从头开始计算连续的整数数量，直到找不到连续的整数
                currentNumberConsecutiveNumberLength++;
            }

            // 比较「最长连续整数长度」与「目前整数为起点，连续整数的长度」，取最长的那一个
            longestConsecutiveNumberLength = Math.max(longestConsecutiveNumberLength, currentNumberConsecutiveNumberLength);
        }
    });


    return longestConsecutiveNumberLength;
};

参考资料