[LeetCode/Java] 169. Majority Element

0. 문제

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

1. 문제 설명

• 정수 배열 nums가 주어질 때 majority element를 반환하라.
• majority element란, 전체 배열 중 절반 이상 등장하는 원소다.

2. 문제 풀이

2.1. 접근법

• majority element는 전체 배열 중 절반 이상 등장하는 원소다.
• 따라서, 배열을 정렬한 후 중간에 위치한 원소가 majority element가 된다.

2.2. 의사코드

nums 오름차순 정렬
return nums[중간 인덱스]

3. 코드

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

4. 결과

5. 개선점

5.1. 시간 복잡도 개선

• 정렬을 했기 때문에 시간 복잡도는 O($nlogn$)이다.
• Boyer-Moore 과반수 투표 알고리즘을 사용하면 O($n$) 시간 복잡도로 해결 가능하다. (참고)
• 코드

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int ans = 0;
        
        for (int i : nums) {
            if (count == 0) {
                ans = i;
            }
            
            if (ans == i) count++;
            else count--;
        }
        return ans;
    }
}

• 결과