LeetCode 169. Majority Element

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

 

 

 

풀이

문제에서  n/2 기준으로 넘는 수를 출력하라했는데  값 리턴값이 1개인걸 보고 출현빈도가 제일 높은 값을 나타나면 되겠구나 라고 생각했다.

 

딕셔너리를 생성하여 nums를 순회하며 각각의 값으로 딕셔너리에 키 값을 생성하고, 중복되는 숫자가 나온다면 값을 증가시켰다 ,

이후에 딕셔너리의 값 중 가장 큰 값의 키를 리턴시켰다. 

 

nums의 리스트에서 max 메소드를 이용하여 가장 큰 값을 뽑아 

list = [0] * (max(nums)+1) 로 방문리스트를 만들어서 max(list)를 통해 값을 나오게하는 방법도 생각났지만 문제의 조건에

음수 값까지 포함되기에 딕셔너리를 사용했다 .

 

class Solution(object):
    def majorityElement(self, nums):
        dict={}          #딕셔너리 생성 
        for n in nums:   # nums숫자 for문으로 순회 
            if n not in dict: # n이 딕셔너리안에 존재하지 않는다면 
                dict[n] = 1   # 키:값 생성
            else:
                dict[n]+=1    # 존재한다면 해당 키의 값 +1

        return (max(dict,key=dict.get))  # 딕셔너리의 값 중 가장 큰 값의 키 리턴​
        
        
#sudo 

  def majorityElement(self, nums):
        dict={}          #딕셔너리 생성 
        for n in nums:   # nums숫자 for문으로 순회 
            if n not in dict: # n이 딕셔너리안에 존재하지 않는다면 
                dict[n] = 1   # 키:값 생성
            else:
                dict[n]+=1    # 존재한다면 해당 키의 값 +1

        return (max(dict,key=dict.get))  # 딕셔너리의 값 중 가장 큰 값의 키 리턴​

 

 

조회수가 가장 높은 python 코드

 

#1
def majorityElement1(self, nums):
    nums.sort()
    return nums[len(nums)//2]
    
    
    
#2
def majorityElement(self, nums: List[int]) -> int:
    majorityMap = Counter(nums)
    return max(majorityMap, key=majorityMap.get)

첫번째는 배열의 가장 큰 값은 중앙에 있기에 정렬 후 가운데 위치에 있는 수를 가져오는 방법이지만 예외케이스 발생

ex) arr = [2,2,5,5,1,1,10,10,11,11,11] sorted(arr)[len(arr)//2]는 11이 아닌 5를 반환

 

두번째는 counter 메소드를 사용해서  dict를 사용해서 만든 방법과 동일하게 사용