algo-wiki

Appearance

Majority Element (LeetCode 169) ​

문제 링크 → LeetCode 169. Majority Element

문제 설명 ​

정수 범위 nums가 주어지면, 배열 내에서 과반수(> n/2번 등장)하는 요소를 찾아 반환합니다. 문제 조건상, 과반수 요소는 반드시 존재합니다.

입력 ​

  • nums: 정수 배열 (length >= 1)

출력 ​

  • 배열에서 과반수로 등장하는 정수

접근 방법 ​

1. Map 자료구조 사용 ​

  • 각 숫자의 등장 횟수를 Map에 저장
  • 과반수 조건을 충족하면 바로 반환

2. Boyer-Moore Voting Algorithm ​

  • 공간 복잡도를 O(1)로 줄인 방법
  • 하나의 후보와 카운트만 사용

풀이 코드 ​

1. Map 사용 ​

typescript
function majorityElement(nums: number[]): number {
  const halfLen = nums.length / 2
  const map = new Map<number, number>()

  for (const num of nums) {
    const cnt = (map.get(num) ?? 0) + 1
    map.set(num, cnt)

    if (cnt > halfLen) return num
  }

  throw new Error('No majority element found')
}
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(n)

2. Boyer-Moore Voting Algorithm ​

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

  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i]
      count = 1
    } else if (nums[i] === candidate) {
      count++
    } else {
      count--
    }
  }

  return candidate
}
  • 시간 복잡도: O(n)
  • 공간 복잡도: O(1)

시간/공간 복잡도 비교 ​

방법시간 복잡도공간 복잡도
Map 사용O(n)O(n)
Boyer-Moore Voting AlgorithmO(n)O(1)

요약 ​

  • 배열을 한 번만 순회하면서 과반수 원소를 찾을 수 있다.
  • 공간 복잡도 최적화를 원하면 Boyer-Moore 알고리즘이 적합.