[Misc][Easy] 169. Majority Element

https://leetcode.com/problems/majority-element/description

 

Q. 주어진 정수 배열 nums에서 빈도수가 배열 길이의 반이상이 되는, 대다수가 되는 정수를 찾아라.

 O(N)의 TC에 O(1)의 memory space를 사용하라.

 

 

Solution. 

 추가 버퍼를 쓸 수 있다면 간단하다. frequency buffer를 만들고 가장 큰 녀석을 찾는다. 

 

 정렬해서 가운데 위치하는 녀석을 반환해도 된다. 반 이상 빈도가 되므로 가능한 것이다. 하지만 TC가 O(NxLogN) 이다. 

 

 다른 접근이 필요하다. 

 boyer-moore voting 알고리즘으로 풀이를 시도 해 본다. 

 

 즉, 0을 기준으로 후보를 정한다. 

 후보와 같으면 1을 더하고 아니면 1을 뺀다. 

 다시 이 누적값이 0이 되면 그때의 배열 값으로 후보를 재설정 한다. 

 

 그 후보 값이 만약 배열에서 반이상 출현했다면 그것이 정답이 된다. 

 (문제에서는 반드시 이 값이 존재한다고 했으므로 검증까지는 필요없다. )

 

 로직대로 코드를 만든다. 

 

 

public int MajorityElement(int[] nums) 
{
    int cnt = 0;
    int candidate = 0;
    for(int q = 0; q < nums.Length; ++q)
    {
        if(cnt == 0)
            candidate = nums[q];

        cnt += nums[q]==candidate ? 1 : -1;
    }

    int mid = (int)(nums.Length * 0.5f);
    for(int q = 0; q < nums.Length ; ++q)
    {
        if(nums[q] == candidate)
            --mid;

        if(mid <= 0)    return candidate;
    }
    return -1;
}

 

적절한 결과를 얻었다. 

이 문제는 위 제한이 있을 시 알고리즘에 의존해야 하므로, medium 난이도, 제한이 없다면 easy 이다.

 

Reference : https://an-thropology.tistory.com/6