text: """
  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 
  
  # 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]