[알고리즘] LeetCode - Majority Element

Majority Element - LeetCode

문제 설명

• 정수형 배열 nums가 주어진다.
• nums 배열의 수 중에서 주된 요소 (매번 n/2보다 큰 갯수를 가진 수)를 반환해야 한다.

문제 해결

• 반복문을 돌면서 count Map에 수의 갯수를 카운팅한다.
• 카운트를 올리면서 갯수가 N / 2 (N은 배열의 길이) 보다 큰 경우 answer 값을 갱신하고 반복문을 중지한다.
• 배열의 길이가 1인 경우에는 반복문을 돌 필요가 없기 때문에 상단에서 nums 배열의 1번 째 값을 반환한다.

시간 복잡도

• O(N)

풀이 코드

import java.util.*;

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        int N = nums.length;
        int answer = 0;

        if (N == 1) {
            return nums[0];
        }

        for (int i = 0; i < N; i++) {
            int now = nums[i];
            if (!count.containsKey(now)) {
                count.put(now, 1);
            } else {
                int c = count.get(now) + 1;

                if (c > N / 2) {
                    answer = now;
                    break;
                }

                count.put(now, c);
            }
        }

        return answer;
    }
}

결과

시간	메모리
13 ms	46.6 MB