LeetCode - 169. Majority Element

How to effectively use LeetCode to prepare for interviews!! - LeetCode Discuss

https://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 appears more 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

---

배열에서 다수를 차지하는 배열 요소를 찾는 문제이다.

 

다수를 찾기 위해선 배열을 한바퀴 돌아야한다.

 

문제의 조건에서 다수를 차지하는 요소는 전체 배열의 반 이상 나타난다고 한다.

 

그럼 n/2를 넘은 수는 배열을 다 돌 필요없이 return 하면 될 것 같다.

 

그럼 각각 배열의 요소가 몇 개씩 있는지 알려면 어떻게 해야될까?

 

배열을 오름차순 정렬하여 종류가 달라지면 다른 요소라고 생각하고 같으면 하나 더 있다고 생각하자.

 

그렇게 같은 요소의 count를 세고 다음 종류의 수가 count 보다 많으면 count를 갱신한다.

 

import java.util.*;
class Solution {
    public int majorityElement(int[] nums) {
        int maxCount = 0;
        int count = 0;
        int element = 0;
        
        Arrays.sort(nums);
        
        if(nums.length == 1){
            return nums[0];
        }
        
        for(int i = 0 ; i < nums.length-1 ; i++){
            if (nums[i] == nums[i+1]){
                count++;
                if(count >= nums.length/2){
                    return nums[i];
                }
            }else{
                if (maxCount < count){
                    maxCount = count;
                    count = 1;
                    element = nums[i];
                }
            }
        }
        
        return element;
    }

}

 

엣지 케이스는 nums 가 한개 짜리 배열일 때 이다. 

그땐 바로 리턴해준다.

 

Success

Details 

Runtime: 3 ms, faster than 52.83% of Java online submissions for Majority Element.

Memory Usage: 43 MB, less than 25.73% of Java online submissions for Majority Element.

 

무어의 알고리즘을 이용해도 된다.

 : 다수 원소의 출현횟수의 총합은 나머지 원소의 출현횟수보다 많다

 

Boyer-Moore majority vote algorithm

Boyer–Moore majority vote algorithm - Wikipedia

그말은 즉 Sort를 했을때 한 가운데 있는 배열 요소는 항상 Majority 요소가 될것같은데..

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

Success

Details 

Runtime: 1 ms, faster than 99.90% of Java online submissions for Majority Element.

Memory Usage: 42.7 MB, less than 52.21% of Java online submissions for Majority Element.

 

통과된다ㅋㅋㅋ