169. Majority Element

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

그냥 풀었던 버전 -> 요렇게 풀면 정렬 때문에 시간 복잡도가 O(nlogn)이 나온다.

코드

function majorityElement(nums: number[]): number {
  return nums.sort((a, b) => a - b)[Math.floor(nums.length / 2)];
}

시간 복잡도

시간 복잡도: O(nlogn)

풀이 2 - Boyer–Moore Voting Algorithm

코드

function majorityElement(nums: number[]): number {
  let count = 0;
  let candidate = 0;

  for (let idx = 0; idx < nums.length; idx++) {
    // count가 0인 경우에는 현재 요소를 새로운 후보로 설정하고 count = 1
    if (count === 0) {
      candidate = nums[idx];
      count = 1;
    } else {
      candidate === nums[idx] ? count++ : count--;
    }
  }

  return candidate;
}

시간 / 공간 복잡도

시간 복잡도: O(n)
공간 복잡도: O(1)

169. Majority Element

문제

풀이 1

아이디어

코드

시간 복잡도

풀이 2 - Boyer–Moore Voting Algorithm

코드

시간 / 공간 복잡도