Leetcode 229. Majority Element II

题目描述：找出数组中超过向下取整n//3的数

题目链接：Leetcode 229. Majority Element II

题目思路：跟之前n//2的众数不一样的是这里不保证有众数而且可能为空。
还是使用投票法，但是这个要投出2个数字出来，最多，最少0个。所以设置两个计数器。
c1、c2候选者和cnt1、cnt2计数器，当其中一个计数器为0的时候，就把n置位，并初始化计数器，如果碰到相等的就+1 不等的就两个都减1抵消掉。这样最后的两个候选者一定是最多的两个，但是不保证是大于n//3的次数，所以得检查一下。

思路：既然最多元素出现了n/2次，那我就想用抵消的思想，用它和与它不相等的元素一一相消，剩下的一定就是最多的那个元素。根据这个想法，有了如下代码。

关于Majorty Element题目的补充位操作法：

public int majorityElement(int[] nums) {
        int[] bits = new int[32];
        for(int num : nums){
            for(int i=0; i<32; i++){
                if((num >>i & 1) == 1){
                    bits[i]++;
                }
            }
        }
        
        int conditionNum = nums.length / 2;
        int result = 0;
        for(int i=0; i<32; i++){
            if(bits[i] > conditionNum){
                result += (1 << i);
            }
        }
        return result;
    }
//时间复杂度O(n)
//空间复杂度O(1)

代码如下

class Solution:
    def majorityElement(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums:
            return []
        ans = []
        cnt1 = 0
        cnt2 = 0
        c1 = 0
        c2 = 0
        for n in nums:
            if n==c1:
                cnt1 += 1
            elif n==c2:
                cnt2 += 1
            elif cnt1 == 0:
                c1 = n
                cnt1 = 1
            elif cnt2 == 0:
                c2 = n
                cnt2 = 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        cnt1 = cnt2 = 0
        for n in nums:
            if n==c1:
                cnt1 += 1
            elif n==c2:
                cnt2 += 1
        if cnt1 > (len(nums)//3):
            ans.append(c1)
        if cnt2 > (len(nums)//3):
            ans.append(c2)
        return ans
       

参考链接

• [Leetcode] Majority Element 众数
• [LeetCode] Majority Element II 求众数之二