problem

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.题目大意：给定一个长度为n的数组，寻找其中的“众数”。众数是指出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且数组中的众数永远存在。

解答

• 此想法
  循环嵌套 ==nums.count(x)== 时间复杂度过高

class Solution(object):    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: int        """        for x in nums:            if nums.count(x) > len(nums)/2:                return x

• 考虑 二分 set等方式

class Solution(object):    def majorityElement(self, nums):        """        :type nums: List[int]        :rtype: int        """        length = len(nums)/2        listelement = set(nums)        for x in listelement:            if nums.count(x) > length:                return x

写的很粗糙，这个link比较分明

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithmhttp://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html