169.Majority Element - Leetcode

In [1]:

import sys
from collections import Counter, defaultdict
sys.path.append("/home/swyoo/algorithm")
from utils.verbose import logging_time

169. Majority Element

leetcode

Given an array of size n, find the majority element. The majority element is the element that appears more than $⌊ n/2 ⌋$ times.
You may assume that the array is non-empty and the majority element always exist in the array.

Divide and Conquer

majority element가 항상 존재한다는 것에 주목하면, left또는right는 그 범위 안에서 항상 정답이다.
또한, majority element는 $⌊ n/2 ⌋$ 이상 발생한 숫자이므로, cross하는 경우에 대해서 left아니면 right가 답이 된다.
majority element는 count를 통해 알 수 있다.
left(nums[s..mid]의 majaority element), right(nums[mid+1..e]의 majaority element)를 recursive하게 구해서 안다는 가정하에
nums[s..e]의 majaority element)를 다음과 같이 구한다.

• left와 right가 같다면 그대로 left또는 right를 majority로 한다.
• left와 right가 다르다면 left 와 right 둘 중 하나가 majority이므로 count해보고 결정한다.

In [2]:

class Solution(object):
    # O(nlogn) - divide and conquer 
    @logging_time
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        def dc(s, e):
            if s >= e: return nums[s]
            
            mid = (s + e)//2
            left = dc(s, mid)
            right = dc(mid + 1, e)
            
            # cross
            if left == right:
                return left
            count_left = sum(1 for k in nums[s: e + 1] if k == left)
            count_right = sum(1 for k in nums[s: e + 1] if k == right)
            return left if count_left > count_right else right
        
        return dc(0, len(nums)-1)
    
    # O(n) - use hashmap
    @logging_time
    def majorityElement_v2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
#         def f(x, H):
#             H[x] += 1
#         H = defaultdict(int)
#         map(lambda e: f(e, H), nums)
#         return max(H.keys(), key=lambda x: H[x])
        counts = Counter(nums)
        return max(counts.keys(), key=counts.get)

In [3]:

sol = Solution()

In [4]:

A = [2,2,1,1,1,2,2]
print(sol.majorityElement(A, verbose=True))
print(sol.majorityElement_v2(A, verbose=True))

WorkingTime[majorityElement]: 0.01216 ms
2
WorkingTime[majorityElement_v2]: 0.07081 ms
2