Majority Element

Majority Element

크기 n의 배열 num이 주어지면 대부분의 요소를 반환합니다. 다수 요소는 [n/2]회 이상 나타나는 요소입니다. 대부분의 요소가 배열에 항상 존재한다고 가정할 수 있습니다. 즉 이 문제는 n/2회 이상 나타나는 최빈값을 찾는 문제입니다.

입출력 예제

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

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

나의 풀이

class Solution(object):
  def majorityElement(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    dic = dict() # 딕셔너리 자료형
    for i in list(set(nums)): # 유니크한 값을 추출하기 위해 세트 자료형으로 변환하여 중복 제거
      dic[i] = 0 # 유니크한 숫자를 키 값으로 하며 밸류(반복횟수)를 0으로 초기화
      for j in nums: # 배열의 모든 요소와 비교
        if i == j: # 만약 값이 같을 경우 반복횟수인 딕셔너리의 밸류값을 1증가
          dic[i] += 1

    max_num = 0 # 가장 큰 빈도 횟수
    result = 0 #  nums의 배열 요소 중 가장 많은 빈도 횟수를 가지는 숫자
    for k, v in dic.items(): # 키와 값을 모두 뽑아내기 위해서 items 함수 사용
      if max_num < v: # 빈도 횟수 비교
        max_num = v # 빈도 횟수가 가장 클 경우 max_num에 가장 큰 빈도수 업데이트
        result = k # 해당 빈도수를 가지는 숫자를 result에 저장

    return result

nums 배열을 세트 자료형으로 한 번 변환하여 중복을 제거하여 유니크한 값들을 nums 배열의 각 요소와 비교하여 값이 같을 경우 딕셔너리 자료형을 사용하여 요소를 키로 반복된 횟수를 값으로 하여 저장합니다. 두 번째 반복문에서는 딕셔너리에 저장된 밸류값 중 가장 큰 밸류값을 찾고 찾은 밸류값을 밸류로 가지는 키를 찾아내어 빈도수가 가장 많은 숫자를 찾아냅니다.

이 코드는 런타임 125ms (71.29%)와 메모리 14.99MB (47.42%) 입니다.

런타임이 가장 최적화된 코드 (0.01% / 96ms)

class Solution(object):
  def majorityElement(self, nums):
    nums.sort()
    return nums[len(nums)//2]

나의 코드는 어떤 조건에서도 최빈값을 찾는 코드였지만 위 코드는 배열의 총 길이에서 절반 이상 나타나는 인수가 존재한다고 가정할 때 최빈값을 찾는 코드이다. 즉, 이러한 가정에서는 배열의 중간값이 최빈값을 나타낼 것이기 때문에 위 코드에서 nums 배열의 중간값을 반환하였다.