Leetcode - Majority Element

Problem

Input: nums = [3,2,3]
Output: 3

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Approach

EN

KR

제한사항에서 nums배열의 길이는 1부터 시작한다고 했으므로 만약 배열의 길이가 1이라면 바로 배열 첫번째 원소를 리턴한다.

그렇지 않다면 주어진 배열의 원소가 정렬되어 있지 않기 때문에, 값의 비교가 어렵다고 생각했다. 배열을 (오름차순으로) 정렬한 뒤 설정해놓은 현재 값과 배열을 순회하고 있는 nums[i]의 값이 같다면 현재 값 카운트, 만약 현재 값과 nums[i]의 값이 같지 않다면 해당 원소의 중복은 끝났으므로 다시 현재 값을 nums[i]로 설정, 카운트는 다시 1부터 시작한다.

하지만 문제는 어떤 값을 가진 원소가 제일 많이 들어가 있냐이기 때문에, 현재 값과 현재 카운트와 비교할 최대 값과 최대 값 카운트가 필요하다. 제일 처음 0으로 설정한 최대값 카운트보다 현재 값 카운트가 크다면,최대 값 카운트는 현재 값 카운트로 당연히 최대 값도 현재 값이 된다.

마지막으로 최대 값을 리턴한다.

❗️ 공간 복잡도는 통과했으나 정렬하는 과정 때문에 시간복잡도에서 O(n)(linear time)에 들어오지 못했다.

code

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
  
  	if(nums.length === 1) {
        return nums[0];
    }
 
    nums.sort((a,b)=> a-b);
  
    let max_cnt = 0;
    let cur_cnt = 0;
    let cur_val;
    let max_val;

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

        if(cur_cnt > max_cnt) {
            max_cnt = cur_cnt;
            max_val = cur_val;
        }
    }

    return max_val;
};

Review

보이어 무어 알고리즘(Boyer-Moore Voting Algorithm) 을 이용해 해당 배열의 원소가 또 있다면 카운트를 늘리고 아니면 카운트를 감소시켜 찾는 방법으로 풀면 O(n)의 시간복잡도를 가지며 아래와 같은 방식으로 동작한다. 사실 어떻게 정렬을 하지않고도 majorValue에 제일 중복이 많이 쌓이는 값이 들어오는지 이해가 80%밖에 되지 않아 추가적으로 더 공부를 할 예정이다.

code

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

    for (let num of nums) {
        if (count === 0) {
            majorValue = num;
            count = 1;
        } else if (majorValue === num) {
            count++;
        } else {
            count--;
        }
    }

    return majorValue;
};