majority-element.py

"""
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.

Example 1:

Input: [3,2,3]
Output: 3
Example 2:

Input: [2,2,1,1,1,2,2]
Output: 2
"""

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

# V1 
# https://blog.csdn.net/NXHYD/article/details/71713772
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(nums)[(len(nums))/2]

# V1' 
# https://blog.csdn.net/NXHYD/article/details/71713772
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        b = {}
        for eachnum in nums:
            if eachnum not in b:
                b[eachnum] = 1
            else:
                b[eachnum] += 1
        for eachnum in b:
            if b[eachnum] == max(b.values()):
                return eachnum
        return 0

# V1''
# http://bookshadow.com/weblog/2014/12/22/leetcode-majority-element/
class Solution:
    # @param num, a list of integers
    # @return an integer
    def majorityElement(self, num):
        candidate, count = None, 0
        for e in num:
            if count == 0:
                candidate, count = e, 1
            elif e == candidate:
                count += 1
            else:
                count -= 1
        return candidate
        
# V2 
# Time:  O(n)
# Space: O(1)
import collections
class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        idx, cnt = 0, 1

        for i in range(1, len(nums)):
            if nums[idx] == nums[i]:
                cnt += 1
            else:
                cnt -= 1
                if cnt == 0:
                    idx = i
                    cnt = 1

        return nums[idx]

    def majorityElement2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return sorted(collections.Counter(nums).items(), key=lambda a: a[1], reverse=True)[0][0]

    def majorityElement3(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return collections.Counter(nums).most_common(1)[0][0]