[ LeetCode ][JAVA][169] Majority Element (과반수알고리즘)

leetcode.com/problems/majority-element/

Majority Element - LeetCode

문제

Given an array of size_n_, find the majority element. The majority element is the element that appearsmore than⌊ n/2 ⌋times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

Example 2:

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

 

해석하자면 어떤 원소가 가장 많이 출연하였는가!

접근

푸는 방법은 총 세가지가 있다.

1. HashMap<Integer, Integer> // label, count
시간:O(n)
공간:O(n)

 

2. 이중 for loop
등장하는 원소마다 등장한 카운트를 체크, 가장 많은 득표한 것을 업데이트
시간:O(n^2)
공간:O(1)

3. 과반수 득표 알고리즘
시간:O(n)
공간:O(1)

en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

Boyer–Moore majority vote algorithm - Wikipedia

// pseudo code
x=null, cnt=0

for each element a:
	if(cnt==0) x=a, cnt++;
    else if(x==a) cnt++;
    else cnt--;

 

투표 종료 후 다음 둘 중 하나는 참
- 과반수 득표가 존재하지 않음
- 과반수 득표는 x

 

예1 : 3, 2, 3
3: x=3, cnt=1
2: x=3, cnt=0
1: x=3, cnt=1
=> 3!

예2 : 3, 2
3: x=3, cnt=1
2: x=3, cnt=1
=> 3!

 

코드

class Solution{
    public int majorityElement(int[] nums){
        int x = 0, cnt = 0;
        for(int num : nums){
            if(cnt == 0) {
               x=num;
               cnt++;
            } else if (x == num){
                cnt++;
            } else {
                cnt--;
            }
        }
        return x;
    }
}