Portfolio

문제

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

Constraints:

0 <= nums.length <= 105

109 <= nums[i] <= 109

풀이

은찬


const longestConsecutive = (nums) => {
    const parent = new Map();
    const {length} = nums;
    let answer = 0;
    
    const unionParent = (x) => {
        const pp = parent.get(x + 1);
        
        if(pp !== undefined){
            parent.set(x, unionParent(pp));
            
            return parent.get(x);
        } else{
            return x;
        }
    }
    
    // initialize
    for(let i = 0; i < length; i++){
        parent.set(nums[i], nums[i]);
    }
    
    // union
    for(let i = 0; i < length; i++){
        unionParent(nums[i]);
    }
    
    // find
    for(let i = 0; i < length; i++){
        const val = parent.get(nums[i]) || 0;
        const count = Math.abs(nums[i] - val) + 1;
        
        answer = answer < count ? count : answer;
    }
    
    return answer;
};

효성


var longestConsecutive = function(nums) {
    if(nums.length <= 1) {
        return nums.length;
    }
    
    const set = new Set(nums);
    
    let longestLen = 1;

    nums.forEach(num => {
        if(!set.has(num) || set.has(num - 1)) {
            return;
        }
        
        let curLen = 1;
        set.delete(num);
        
        let nextConsecutiveNum = num + 1;
        
        while(set.has(nextConsecutiveNum)) {
            set.delete(nextConsecutiveNum);
            curLen++;
            nextConsecutiveNum++;
        }
        
        longestLen = Math.max(longestLen, curLen);
    });
    
    return longestLen;
};

재영

object로 풀었어요.

정수 프로퍼티 → 양의 정수면 정렬되는 걸 이용


const longestConsecutive = function (nums) {
  const minusIntegers = {}; // 음의 정수
  const plusIntegers = {}; // 양의 정수

  for (let i = 0; i < nums.length; i += 1) {
    const now = nums[i];

    if (now < 0) {
      minusIntegers[Math.abs(now)] = 0; // 절대값 -1 -> 1
    } else {
      plusIntegers[now] = 0;
    }
  }

  const minusArr = Object.keys(minusIntegers); // [-1, -2, -3, -4]
  const plusArr = Object.keys(plusIntegers); // [1,2,3,4]

  let last; // 이전 값을 캐싱.
  let nowCount = 0; // 현재 개수
  let maxCount = 0; // 최대 개수

  const check = (prev, now) => !!(parseInt(prev) === parseInt(now - 1));
  const updateValue = (now) => {
    if (last === undefined) {
      last = now;
      nowCount = 1;

      return;
    }

    if (!check(last, now)) {
      maxCount = Math.max(nowCount, maxCount);
      nowCount = 1;
    } else {
      nowCount += 1;
    }

    last = now;
  };

  while (minusArr.length) {
    const now = -1 * minusArr.pop();

    updateValue(now);
  }

  for (let i = 0; i < plusArr.length; i += 1) {
    const now = plusArr[i];

    updateValue(now);
  }

  return Math.max(maxCount, nowCount);
};

Longest Consecutive Sequence

문제

풀이