[LeetCode] 169. Majority Element

👿 문제 169. Majority Element

nums 배열에서 빈도수가 높은 숫자 return 하기

😈 풀이

✔️ 첫번째 풀이

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let map = new Map()

    for (let i = 0; i < nums.length; i++) {
        let getMap = map.get(nums[i])
        if (!getMap) {
            map.set(nums[i], 1)
            continue;
        }

        map.set(nums[i], getMap + 1)
    }

    let maxKey = 0
    let maxNum = 0
    for (let [key, value] of map) {
        if (value > maxNum) {
            maxKey = key
            maxNum = value
        }
    }

    return maxKey
};

1. Map을 이용해서 map 객체를 생성한다.
2. nums를 순회하며 map 객체에 요소가 있는지 확인 후 없으면 value를 1로 set 해준다.
3. 있으면 기존 value + 1
4. map의 key, value를 순회하면서 value가 maxNum보다 크면 maxKey를 key, maxNum을 value로 설정한다.
5. 최종 maxKey를 반환한다.

시간복잡도 : O(n) // Map O(n) + for문 O(n) + for문 O(n)
공간복잡도 : O(n) // Map O(n)

✔️ 두번째 풀이

Follow-up! 공간복잡도 O(1)로 만들어보기

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
    let majNum;
    let count = 0;

    for (let num of nums) {
        if (count === 0) {
            majNum = num
        }

        count += majNum === num ? 1 : -1
    }

    return majNum
};

1. majNum 선언, count=0 으로 초기화 해준다.
2. nums를 순회하며 count가 0이 될 때 majNum을 변경해준다.
3. majNum, num이 같으면 count +1, 다르면 -1을 해준다.
4. 최종 majNum을 반환한다.

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

Boyer-Moore 투표 알고리즘을 통해 공간복잡도를 O(1)로 줄이고 runtime은 10ms 줄였다!

Boyer-Moore 투표 알고리즘이란?
➡️ 원소들 중 절반 이상 포함된 원소를 linear time, constant space로 찾을 수 있는 알고리즘. 과반수 이상의 원소가 존재한다는 보장이 될 때, 결과값은 항상 과반수에 해당하는 원소가 된다.
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majorityvote_algorithm

✅ 1일1알