[LeetCode] Array101 - Third Maximum Number

Third Maximum Number

Given integer array nums, return the third maximum number in this array. If the third maximum does not exist, return the maximum number.

 

Example 1:

Input: nums = [3,2,1]
Output: 1
Explanation: The third maximum is 1.
Example 2:

 

Example 2:

Input: nums = [1,2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:

 

Example 3:

Input: nums = [2,2,3,1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number.
Both numbers with value 2 are both considered as second maximum.

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

Follow up: Can you find an O(n) solution?

 

---

 

이제 2문제만 더 풀면 Array101 시리즈가 끝이 난다.. 🎉

 

일단 이번주에 푼 문제 중에 제일 재밌었던 문제를 적어보려고 한다.

주어진 배열 중에서 3번째로 큰 숫자를 찾아내고, 만약 3번째로 큰 숫자가 없다면 첫 번째로 큰 숫자를 리턴하는 문제이다.

중요한 점은 중복 숫자는 제외해야한다.

 

sort나 filter 메소드를 사용하면 금방 풀겠지만 중요한건 시간 복잡도가 O(n)이어야한다는 점이다.

 

일단 filter와 Math.max 메소드를 사용해서 푼 방법은 다음과 같다.

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
  let filtered = nums;
  let max = Math.max(...nums);
  const result = [max];

  for (let i = 0; i < 2; i++) {
    filtered = filtered.filter(num => num !== max);
    if (filtered.length === 0) return result[0];

    max = Math.max(...filtered);

    result.push(max);
  }

  return max;
};

 

제일 큰 숫자를 찾아내고, 해당 숫자를 배열에서 전부 제거한다.

이걸 3번 반복하면 3번째로 큰 숫자가 나온다.

만약 3번째로 큰 숫자가 없다면 제일 큰 숫자를 리턴한다.

 

이 방법의 문제점은 filter를 반복하면서 계속 loop을 돈다는 것이다.

딱 한 번만 loop을 돌면서 세번째로 큰 숫자를 찾아내야하기 때문에 다른 방법을 고민해보았다.

 

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
  let first = nums[0];
  let second = null;
  let third = null;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > first) {
      third = second;
      second = first;
      first = nums[i];
    } else if (second === null || nums[i] > second) {
      if (nums[i] !== first) {
        third = second;
        second = nums[i];
      }
    } else if (third === null || nums[i] > third) {
      if (nums[i] !== second) {
        third = nums[i];
      }
    }
  }

  return third === null ? first : third;
};

 

그게 바로 이 방법인데,

변수를 3개 만들어서 숫자가 큰 순서대로 담는 방법이다.

 

근데 아무래도 if문 조건이 복잡해서 조금 코드가 지저분하게 보이는데,

LeetCode에 답을 submit하고 다른 사람이 푼 코드를 둘러보다가 아주 획기적인 방법을 발견했다.

 

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var thirdMax = function(nums) {
  let first = nums[0];
  let second = -Infinity;
  let third = -Infinity;

  for (let i = 1; i < nums.length; i++) {
    if (nums[i] > first) {
      third = second;
      second = first;
      first = nums[i];
    } else if (nums[i] < first && nums[i] > second) {
      third = second;
      second = nums[i];
    } else if (nums[i] < second && nums[i] > third) {
      third = nums[i];
    }
  }

  return third === -Infinity ? first : third;
};

 

위에 내가 푼 방법과 거의 유사하지만,

second와 third의 초기값을 -Infinity로 한다는 점이 넘나 굿 아이디어! 👍

Infinity는 다른 어떤 수보다 크기 때문에 -Infinity는 다른 어떤 수보다 작다는 것을 활용해서 푼 방법이다.