[LeetCode] 169. Majority Element

Problem

Majority Element

Solution

Hint

• 시간 복잡도 O(1)
• 원소별 카운팅

위 두 keyword 로 바로 떠오르는 자료구조가 있어야 한다, 바로 Map 이다.

key 로는 element를, value 로는 element 별 counting 을 진행하면 된다.

그리고, 가장 카운팅이 많이 된 원소를 반환해야 하므로 조회에 유용한 Map.Entry 까지 사용하면 되는 간단한 문제이다.

이때, 유의할 점은 Collectors.counting() 이 Long data type 을 반환한다는 점이다.

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        List<Integer> lists = Arrays.stream(nums)
        .boxed()
        .collect(Collectors.toList());

        Map<Integer, Long> numToCountMap = lists.stream()
        .collect(Collectors.groupingBy(
            Function.identity(), Collectors.counting())
        );

        Map.Entry<Integer, Long> maxNumToCountMap = numToCountMap.entrySet().stream()
        .max(Map.Entry.comparingByValue())
        .orElse(null);

        return maxNumToCountMap.getKey().intValue();
    }
}