[leetcode #169] Majority Element

Problem

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 * 10⁴
・ -2³¹ <= nums[i] <= 2³¹ - 1

Follow-up: Could you solve the problem in linear time and in O(1) space?

Idea

주어진 배열에서 빈도수가 가장 높은 수를 찾으라는 문제다.

수를 key로 하고 빈도수를 value로 하는 map을 사용하면 쉽게 풀 수 있다. 배열의 길이의 반보다 빈도수가 더 크다면 곧바로 리턴하면 된다.

Time Complexity: O(n)
Space Complexity: O(n)

Space Complexity를 O(1)로 해서 푸는 방법도 존재한다. Boyer-Moore Voting Algorithm을 이용하면 되는데, 특정 수를 후보로 넣고 count를 세는데 다른 수가 나오면 1을 빼는 방식이다. count가 0이 되면 후보가 되는 수를 교체하고 마지막으로 남는 수를 리턴하면 된다.

Solution

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int num : nums) {
            int cnt = map.getOrDefault(num, 0);
            map.put(num, cnt+1);
            if (cnt >= nums.length / 2) {
                return num;
            }
        }

        return 0;
    }
}

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        Integer candidate = null;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }
}

Reference

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