[Easy] LeetCode - no.169 Majority Element : Java

https://leetcode.com/problems/majority-element/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

과반수를 차지하는 숫자를 return할 것

(n / 2보다 많이 출현하는 숫자 찾기)

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

 

 

 

풀이

import java.util.*;
import java.util.Map.*;

class Solution {
    public int majorityElement(int[] nums) {
        int len = (nums.length % 2 == 0) ? nums.length / 2 : nums.length / 2 + 1;
        Map<Integer, Integer> map = new HashMap<>();

        for (int n : nums) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }

        for (Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() >= len) {
                return entry.getKey();
            }
        }

        return 0;
    }
}

 

• HashMap 사용
• map에 key값과 함께 count 값을 value로 저장
• Entry를 사용하여 entry.getValue()가 len 이상인 경우 해당 key값을 리턴하도록 함
• 시간복잡도 : O(N)

 

 

더 좋은 방법에 대한 고민

• 절반 이상을 차지하는 숫자라면 정렬한 후 가운데 자리를 무조건 차지할 것!

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