[LeetCode/Top Interview 150] [Array / String] 169. Majority Element

문제 링크: https://leetcode.com/problems/majority-element/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: easy

문제:

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3
Example 2:

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

Constraints:

n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109

전략:

전체 배열의 절반 이상을 차지하는 Majority element가 항상 존재한다.
빈도수를 나타내는 HashMap에 저장하고 확인한다면 간단하게 구현할 수 있을 것이다.
n/2 넘기면 바로 return하면 효율적일듯

Follow-up: Could you solve the problem in linear time and in O(1) space?
O(1)의 공간복잡도와 선형 시간 복잡도로 풀 수 있는 가장 빠르고 효율적인 방법은?

코드 구현:

class Solution {
    public int majorityElement(int[] nums) {
        int majority = nums.length/2;
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        
        for (int i=0;i<nums.length;i++) {
            int value = map.getOrDefault(nums[i],0);
            if (majority <= value) {
                return nums[i];
            }
            map.put(nums[i],value+1);
        }
        return -1;
    }
}

실행결과:
Time: 11 ms (35.87%), Space: 46.7 MB (84.76%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0169-majority-element/0169-majority-element.java

개선 방안:

공간복잡도는 괜찮지만 시간복잡도가 문제
Arrays.sort()로 정렬 후 카운팅하기

class Solution {
    public int majorityElement(int[] nums) {
        int majority = nums.length/2+1;
        int pos = 0;
        Arrays.sort(nums);
        
        for (int i=1;i<nums.length;i++) {
            if (nums[i]!=nums[i-1]) {
                // 서로 다른 숫자 경계지점
                if ((i-pos)>=majority) {
                    return nums[i-1];
                }
                pos = i-1;
            }
        }
        return nums[nums.length-1];
    }
}
Accepted	4 ms	48.8 MB	java

Discuss 탭의 타인 코드:

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n/2];
    }
}
// 과반수 넘으니 딱 절반 위치 잡으면 무조건 해당 값인 것 이용
// -> 막상 성능은 내가 개선했던 코드와 생각만큼 큰 차이는 없음(작은 범위에서 실행해서인지)
	Accepted	3 ms	48.6 MB	java

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = 0;
        
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        
        return candidate;
    }
}
Accepted	1 ms	48.9 MB	java
// 현재 체크중인 후보가 맞다면 카운트+, 아니라면 -하여 카운트
// 중간에 후보가 바뀌게 되더라도 결국 마지막에는 과반수인 수(후보)와 +의 카운트 값을 가지게 됨

회고:
시간 복잡도의 측면에서 추가 목표를 달성하는 코드를 보고 정말 발상의 전환이 중요하다고 느꼈다.