[C] LeetCode 169. Majority Element

문제(원문)

문제(번역)

크기가 n인 nums 배열이 주어질때, majority 요소를 반환해라.

majority 요소는 n/2 이상 등장하는 원소로, majority 요소는 항상 배열에 등장한다고 가정해라. 

이 문제를 선형 시간과 O(1)의 공간복잡도로 풀어라.

 

접근 방법

이 문제에서는 majority 요소가 n/2 번 이상 등장한다고 보장이 되어 있다.

아무 수를 잡고 해당 수의 등장 횟수를 증감시키다가, 등장횟수가 0이 되면 다른 수로 교체하는 방법을 반복해서 사용하면 majority 요소를 구할 수 있다.

소스 코드

int majorityElement(int* nums, int numsSize) {
    int num, cnt=0;
    for(int i=0;i<numsSize;i++) {
        if(cnt==0) num = nums[i];
        if(num == nums[i]) cnt++;
        else cnt--;
    }
    return num;
}

 

추가적인 변수도 단 2개만 사용했으므로 공간복잡도는 O(1)이 되며 시간복잡도는 배열을 순회하므로 O(n)이 될 것이다.