[PS] Leet | 128. 가장 긴 연속 수

문제

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.

예시

Example 1:
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.

 

Example 2:
Input: nums = [0,3,7,2,5,8,4,6,0,1]
Output: 9

Example 3:
Input: nums = [1,0,1,2]
Output: 3

조건

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

답

정석적인 풀이 입니다.

 

배열을 정렬한 뒤 순회하면서 뒷 요소와 1씩만 차이나는 (=연속적인) 요소가 나올 때 마다 cnt 증가,

 

그렇지 않은 요소가 나오면 cnt 초기화를 시킵니다.

 

순회하면서 가장 큰 cnt값을 구해 반환하면 됩니다.

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    if (nums.length === 0) return 0;
    let maxLen = 1;
    let cnt = 1;

    nums.sort((a, b) => a - b);
    for (let i=1; i<nums.length; ++i) {
        if (nums[i] === nums[i-1] + 1) {
            cnt++;
            maxLen = Math.max(maxLen, cnt);
        } else if (nums[i] !== nums[i-1]) {
            cnt = 1;
        }
    }

    return maxLen;
};

시간 복잡도 : O(nlogn)

공간 복잡도 : O(n)

 

아래는 O(n)의 풀이입니다.

 

이 경우 JavaScript의 Set이 Hash set임을 이용합니다(Hash의 경우 요소를 찾는 시간이 O(1)입니다).

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestConsecutive = function(nums) {
    const numSet = new Set(nums);
    let maxLen = 0;

    for (const num of numSet) {
        if (!numSet.has(num-1)) {
            let len = 0;
            let cur = num;

            while(numSet.has(cur)){
                len++;
                cur += 1;
            }

            maxLen = Math.max(maxLen, len);
        }
    }

    return maxLen;
};

시간 복잡도 : O(n)

공간 복잡도 : O(n)