리트코드 169 다수원소 // 배열, 투표알고리즘

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

 

* 풀이1

절반이상인 원소가 반드시 존재함을이용

정렬 -> 중간지점의 원소가 다수원소임

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

O(nlgn)

 

* 풀이2

투표 알고리즘 이용 

O(n)

class Solution {
    public int majorityElement(int[] nums) {
        int king=nums[0];
        int cnt=1;

        for(var num : nums){
            if(num==king){
                cnt++;
                continue;
            }
            cnt--;
            if(cnt==0){
                king=num;
                cnt=1;
            }
        }
        return king;
    }
}