[Leetcode] 169. Majority Element

Identifying the Problem

최빈값을 찾아라

단 최빈값은 배열 길이 절반 이상 있다.

 

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

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

Organizing thoughts

바로 떠오르는 알고리즘이 있긴 한데, O(n²)로 상당히 복잡하고 뻔함
그래서 발견한 게 Boyer-Moore 알고리즘임

그림만 봐도 직관적으로 이해가 된다.

main idea : count 가 가장 높았을 때, major의 값이 return 된다.

1. 1부터 마지막만큼 반복하면서

2. major와 nums [i]가 같다면
    2-1 count를 증가 

3. 다르다면
    3-1 count--;

4. count 가 0이 되는 순간 major =  nums[i]
5. major값을 return

Sourcecode

int majorityElement(int* nums, int numsSize)
{
    int major = nums[0];
    int count = 1;
    
    for(int i=1; i<numsSize; i++) //1
    {
        if(major == nums[i]) //2
            count++;
        else                //3
            count--;
        
        if(count == 0)  //4
        {
            major = nums[i];
            count++;
            
        }   
    }
    
    return major; //5
}

 

New things learned

• Boyer-Moore 알고리즘