[Leetcode Top Interview 150] 169. Majority Element

난이도 : easy

문제링크

• int 배열에서, 가장 많이 등장한 숫자를 리턴하라
  • 2/n번 이상 나타나야 한다

 

1. 접근법

• 두번째 원소부터 반복하면서 배열의 원소를 순회한다
• map을 이용하여 원소별 카운트를 저장한다
• 카운트를 내림차순으로 정렬하고, 첫번째 원소를 리턴한다

 

2. 의사코드

for (int i = 0; i < nums.length; i++) {
    map에 원소별 원소 갯수 put
}

for (Map.Entry<Integer, Integer> entry : map을 value의 내림차순으로 정렬한 list) {
    return entry.getKey();
}

return 0;

 

3. 구현 코드

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

    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
    }

    for (Map.Entry<Integer, Integer> entry : map.entrySet().stream().sorted((a, b) -> b.getValue() - a.getValue()).collect(Collectors.toList())) {
        return entry.getKey();
    }

    return 0;
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - 모든 데이터를 순회함
• 공간복잡도 : O(n) - 모든 데이터를 생성해야 함

 

5. 개선점

• 메모리를 O(1)로
• 시간복잡도를 한번의 배열 순회로

 

6. 회고

• 도저히 생각이 안나 풀이를 찾아보았다

int major = nums[0], count = 1;

for (int i = 1; i < nums.length; i++) {
	if (nums[i] == major) {
    	count++;
    } else if (count == 0) {
    	major = nums[i];
        count++;
    } else {
    	count--;
    }
    
    if (count > nums.length/2) {
    	return nums[i];
    }
}

return major;

(출처 : doozi)

 

• 카운트는 major의 출연횟수를 가진다
• 배열을 쭉 순회하면서
  • count가 0이라면, 방문한 원소를 major로 할당하고 count를 하나 늘림
  • major와 다른 원소를 방문한다면, count를 하나 줄임
  • major와 같은 원소를 방문한다면, count를 하나 늘림