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

最原始思路 O(n)

这个方法,也能满足时间限制

  class Solution(object):
      def majorityElement(self, nums):
          """
          :type nums: List[int]
          :rtype: int
          这样的元素只有一个
          而且假定这样的元素一定存在
          """
          tmp = {}
          for item in nums:
              if item not in tmp:
                  tmp[item] = 1
              else:
                  tmp[item] += 1
              if tmp[item]>len(nums)/2:
                  return item

分治法