[LeetCode]229. Majority Element II

Problem

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]
Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

Solution

Analysis

问题要求,返回数组中出现次数超过n/3的数字, 而且时间复杂度为O(N),空间复杂度O(1).

如果没有时间复杂度要求,我们先排序,然后统计每个数字出现的次数,如果符合条件, 加入到结果中;否则,继续查找.

如果在时间复杂度要求和空间复杂度要求下, 可以使用摩尔投票法.

本质上是一种查找{众数(用不是一般情况下的众数n/2,n/3)},超过数组长度一半的数字, 这样数字如果存在,一定只有一个.我们以这个例子,对摩尔投票法进行阐述.

比如[1,2,1,2,3,1,1], 返回结果是1.摩尔投票法是说,现在使用两个变量num,times,分别记录当前数字,当前数字出现的次数. 然后我们依次遍历整个数组,如果下个数字和当前数字相同,times++,更新出现次数; 如果不相同,times–;如果times==0, 更新num和times, num为当前数字,times=1. 如果存在,最后num就是最终的结果.

我们可以将整个统计过程,看做同性相斥,异性相吸: 数字相同,times++; 数字不同,times–. 如果times为0,重新记录. 如果存在符合条件的数字存在,那么因为数字出现次数超过数组长度的一般,num最后剩下的一定是最终结果; 但是,还需要验证一下,判断是否存在. 因为[1,2,3,4,5],这种情况下是不存在的,num=5,错误答案.

根据这个思想,我们可以解决问题. 依据起点不同,可以分为两种方法:

方法一:

res = 0, times = 0

for num in nums:
    if num == res:
        times += 1
    elif num != res:
        times -= 1
    elif times == 0:
        res = num
        times = 1

方法二:

res = nums[0], times = 1

for i in range(1, len(nums)):
    if nums[i] == res:
        times += 1
    elif nums[i] != res:
        times -= 1
    if times == 0:
        res = nums[i]
        times = 1

区别在于: 方法一是成对处理的—三种操作是互斥的.从头开始,

• 如果随机初始化的数字不存在,那么一定跳到times==0执行,然后对times和res正确的初始化;
• 如果存在,那么times更新为1,也是正确地初始化.
• 其他情况,如果出现times=0时,比如[1,2,3]这是后应该是执行到了3, 我们重新对res和times初始化. 跳过了1和2,所以说成对处理的.

方法二是逐个处理的—前两种操作互斥. 第三种处理times=0的处理时机不同.主要是因为我们初始化res,times是有意义的. res初始化为数组中的第一个数字,同时times=1.依次遍历nums[1:]中的数字.

• 如果num == res: times++;
• 否则,times–;
• 其他情况, times==0, 重新赋值,res = num, times = 1. 比如说,[1,2,2], 处理第一个2时,times变为0,此时更新res=2, times=1,然后到第二个2,此时times更新为2.

推荐使用第一种方法.

Code

使用摩尔投票法.这里需要解释一下,如果一个数组中,如果存在出现次数超过n/3的数字,那么最多有两个. 采用反证法,如果多余两个,也就是说3个及以上,假设有3个.那么此时的数组长度至少为: 3 * (n/3),数组长度超过n,不符合条件.

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        // moor voting 摩尔投票法
        vector<int> result;
        if (nums.empty()) return result;
        int a = 0, b = 0, cnt1 = 0, cnt2 = 0, size = nums.size();
        
        for (int num : nums){
            // 各个操作互斥
            if (num == a) cnt1++;
            else if (num == b) cnt2++;
            else if (cnt1 == 0){
                a = num;
                cnt1 = 1;
            }
            else if (cnt2 == 0){
                b = num;
                cnt2 = 1;
            }
            else{
                cnt1--;
                cnt2--;
            }
        }
        
        // count & validate
        cnt1 = 0, cnt2 = 0;
        for (int num : nums){
            if (num == a) cnt1++;
            else if (num == b) cnt2++;
        }
        if (cnt1 > size/3) result.push_back(a);
        if (cnt2 > size/3) result.push_back(b);
        
        return result;
    }
};

References

https://www.cnblogs.com/grandyang/p/4606822.html