【题目描述】

【求众数I】

【方法一】

在不要求时间空间复杂度的情况下，可以采用的方法很多，最简单易懂的一种就是对nums中每个值统计一下数量，如果数量大于nums长度的一半，就直接返回。代码如下：

class Solution(object):    def majorityElement(self, nums):        for i in list(set(nums)):            if nums.count(i)>len(nums)/2:                 return i复制代码

【方法二】

摩尔投票法，是一种多数派想法

1.对于v[i]，如果c此时为未知状态，则c=v[i]，t=1，递增i。

2.如果c==v[i]，++t，递增i。

3.如果c!=v[i]，–t，如果t==0，将c置为未知状态，递增i。

4.所有投票处理完毕后，如果c为未知状态，则说明不存在任何候选人的得票数过半，否则重新遍历数组v，统计候选人c的实际得票总数，如果c的得票数确实过半，则c就是最终结果。

就是这个数在nums中出现次数过半，那么不管如何抵消，最终终会使c等于这个众数，t>=1。时间复杂度O(n),空间复杂度O(1),代码如下：

class Solution(object):    def majorityElement(self, nums):        m=cm=0        for n in nums:            if n==m:                cm+=1            elif cm==0:                m=n                cm=1            else:                cm-=1        return m复制代码