229. Majority Element II

先排序 然后顺序扫描，需要注意边缘，代码如下：

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) <= 1:
            return nums
        if len(nums) == 2:
            if nums[0] != nums[1]:
                return nums
            else:
                return [nums[0]]
        t = len(nums) / 3
        res = []
        nums.sort()
        count = 1
        for i in range(len(nums)):
            if i + 1 < len(nums):
                if nums[i+1] == nums[i]:
                    count += 1
                    if count > t:
                        if nums[i] not in res:
                            res.append(nums[i])
                else:
                    count = 1
        return res

但是这道题目限制了时间是限行时间空间是o(1),因此，既不能使用排序（时间不行） 也不能使用哈希（空间不行）
“
那就是摩尔投票法 Moore Voting，这种方法在之前那道题Majority Element 求众数中也使用了。题目中给了一条很重要的提示，让我们先考虑可能会有多少个众数，经过举了很多例子分析得出，任意一个数组出现次数大于n/3的众数最多有两个，具体的证明我就不会了，我也不是数学专业的。那么有了这个信息，我们使用投票法的核心是找出两个候选众数进行投票，需要两遍遍历，第一遍历找出两个候选众数，第二遍遍历重新投票验证这两个候选众数是否为众数即可，选候选众数方法和前面那篇Majority Element 求众数一样，由于之前那题题目中限定了一定会有众数存在，故而省略了验证候选众数的步骤，这道题却没有这种限定，即满足要求的众数可能不存在，所以要有验证。
”

class Solution:
    # param {integer[]} nums
    # return integer[]
    def majorityElement(self, nums):
        if not nums:
            return []
        num1, num2, time1, time2 = None, None, 0, 0
        for num in nums:
            if num1 == num:
                time1 += 1
            elif num2 == num:
                time2 += 1
            elif time1 == 0:
                num1, time1 = num, 1
            elif time2 == 0:
                num2, time2 = num, 1
            else:
                time1, time2 = time1 - 1, time2 - 1
        numSize = len(nums)
        return [n for n in (num1, num2) if
                n is not None and nums.count(n) > numSize / 3]