问题描述

I. 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.

II. Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋
times. The algorithm should run in linear time and in O(1) space.

问题分析

I. 一开始想设置一个记录字典，然后遍历数组来统计每个元素出现的次数，虽然访问字典的时间复杂度是O(1)，但结果效率不高。看了九章算法的方法，很巧妙。majority element的特点就是其他所有元素的个数加起来都没它多，因此设置一个mj变量记录当前可能成为majority的元素，count记录的是它比其他元素多出现的次数。然而这种方法只在majority element存在的情况下可以，否则它找到的不一定是majority element。
II. 用类似的方法，设置mj1、count1， mj2、count2两个组变量，用相似的方法记录，这样得到的mj1和mj2是出现次数最多的两个元素。最后再进行一次用时O(n)的判断即可。

AC代码

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        mj = None
        count = 0
        n = len(nums)
        for num in nums:
            if count == 0:
                mj = num
                count = 1
            else:
                if num == mj:
                    count += 1
                else:
                    count -= 1
        return mj

Runtime: 56 ms, which beats 81.56% of Python submissions.

class Solution(object):
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        mj1 = None
        mj2 = None
        count1 = 0
        count2 = 0
        for num in nums:
            if num == mj1:
                count1 += 1
            elif num == mj2:
                count2 += 1
            elif count1 == 0:
                mj1 = num
                count1 = 1
            elif count2 == 0:
                mj2 = num
                count2 = 1
            else:
                count1 -= 1
                count2 -= 1

        count1 = 0
        count2 = 0

        for num in nums:
            if num == mj1:
                count1 += 1
            if num == mj2:
                count2 += 1
        rst = []
        if count1 > len(nums)/3:
            rst.append(mj1)
        if count2 > len(nums)/3 and mj2 != mj1:
            rst.append(mj2)

        return rst

Runtime: 60 ms, which beats 82.39% of Python submissions.