一、题目详情

原题目链接
题目详情

二、题目解读

给定一组整数一共n个，同时这些整数中会重复存在
找出某些数字，它在这组数据中重复的次数超过n/3个
示例三 : [1,1,1,3,3,2,2,2]，
n = 8, n/3 = 2 ，找出出现次数超过2的数字(8/3=2.67,向下取整为2)
其中1出现次数3次，3出现次数2次，2出现次数3次
满足条件的数字为1和3

三、解题

  • 暴力解法

    定义一个unordered_map集合，统计所有数字出现的个数
    统计完成后，遍历所有键，将值与n/3比较，取大于n/3的键，返回结果
    时间复杂度O(n),空间复杂度O(n)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution
    {
    public:
        vector<int> majorityElement(vector<int> &nums)
        {
            vector<int> ans;
            int k = nums.size() / 3;
            unordered_map<int, int> map_;
            for (auto i : nums)
                map_[i]++; //如果集合中没有i，那么初始化的值会是0
            for (auto it : map_)
                if (it.second > k)
                    ans.push_back(it.first);
            return ans;
        }
    };

  • 摩根投票法

    1.背景知识：摩根投票法的思想为对拼消耗。

    从最简单的情况入手:
    一次总理选举中,一共有n人投票从m个人,选出获得票为n/2以上的候选人
    容易得出：能满足此条件的最多只有1人,如果有两人，两人票都大于n/2则会比n张票还多
    例如：一人为5票，剩下所有人4票。(假设最坏的情况，剩下的票都在一个人手上)5-4=1>0
    后者限定条件: 选票n/2以上就保证: 获胜者的票 - 剩下不是选他的票 > 0
    因此我们只需2个单位记录： 1个记录name候选人的名字,1个记录count候选人当前相对选票
    实现过程:
    遍历所有选票，初始化候选人为A(第一张票的人) name = A,当前相对选票为1 count = 1
    后面的票分两种情况:

    1.还是A的 :name = A (不变) , count = count + 1
    2.不是A的 :

    (1) A.count > 1 :name = A (不换候选人) ,count = count - 1
(2) A.count = 1 :
    <1>name = B (更换候选人) ,count = 0
    <2>name = A (不更换候选人),count = count - 1 = 0 
(3) A.count = 0 : name = B , count = 1 (选用<2>方法处理才会出现)

    从处理方式我们可能会思考(2)<1><2>两种处理方式的区别会不会导致结果不一样?
    即当A,B同票时，最后的结果都是:

    1. name = A ,count = 0 (相对票数为0)
    2. name = B ,count = 0 (相对票数为0)

    而我们只用了一个name记录名字，但他两的票是一样的，漏了另一个人？
    我们根据限定条件票数大于(n/2)，可知最后的结果一定是有人及时被减掉剩下所有的票，
    他的票还是会大于1的，因此最后的记录的name 持有的票数一定是最多的，且相对票数大于1
    因此两种处理方式都行
    但此方法要注意：剩下count的数量随着位置的变化会不一样
    但是我们需要的只比较count与0的大小。

    2 方法推广

    从基本的情况进行推广：如果有1个人的票k张大于所有票数的一半，
    当遇到所有不是自己票的时候都抵消一张，最后票数一定大于k - (n-k) > 1.
    我们给出两个候选位：

    • 我们每次检测当前元素是否为第一个选中的元素或者第二个选中的元素。
    • 每次我们发现当前元素与已经选中的两个元素都不相同，则进行抵消一次。
    • 如果存在最终选票大于 0 的元素，我们还需要再次统计已选中元素的次数,检查元素的次l数是否大于 n/3.
      如果当前元素在候选元素中，其他的候选元素不需要-1
      候选元素都属于同一阵营（只是不同类别），对抗抵消只作用于不同一阵营

    3 证明方法可行性：

    反证法：若出现次数超过 n/k 的数 xx 最终没有成为候选者。
    有两种可能会导致这个结果：
    1.数值 xx 从来没成为过候选者：

    ​ 如果 xx 从来没成为过候选者，那么在遍历 xx 的过程中，必然有 k−1 个候选者被减了 超过 n/k 次，假设当前 xx 出现次数为 CC，已知 C > n / k，此时总个数为

    ​ (k - 1) C + C = C k

    ​ 再根据 C > n / k，可知 C * k > n，而我们总共就只有n个数，因此该情况恒不成立。

    2.数值 xx 成为过候选者，但被逐出替换了：

    ​ 同理，被逐出替换，说明发生了对 xx 出现次数减一的动作（减到 0），每次的减一操 作，意味着有其余的 k−2 个候选者的出现次数也发生了减一动作，加上本身被遍历到的 当前数 num[i]，共有 k−1 个数字的和 xx 被一同统计。因此，根据我们摩尔投票的处 理过程，如果 xx 成为过候选者，并被逐出替换，那么同样能够推导出我们存在超过 n 个数。

    综上，如果存在出现次数超过 n/k 的数，其必然会成为 k - 1 个候选者之一。

    4 代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    class Solution
    {
    public:
        vector<int> majorityElement(vector<int> &nums)
        {
            vector<int> ans;
            int num1 = nums[0], num2 = nums[0], count1 = 0, count2 = 0;
            for (auto i : nums)
            {
                if (i == num1 && count1 > 0)
                    count1++;
                else if (i == num2 && count2 > 0)
                    count2++;
                else if (count1 == 0)
                {
                    num1 = i;
                    count1 = 1;
                }
                else if (count2 == 0)
                {
                    num2 = i;
                    count2 = 1;
                }
                else
                {
                    count1--;
                    count2--;
                }
            }
            int count11 = 0;
            int count22 = 0;
            for (auto i : nums)
            {
                if (count1 > 0 && i == num1)
                    count11++;
                if (count2 > 0 && i == num2)
                    count22++;
            }
            if (count1 > 0 && count11 > nums.size() / 3)
                ans.push_back(num1);
            if (count2 > 0 && count22 > nums.size() / 3)
                ans.push_back(num2);
            return ans;
        }
    };

三、算法演示

算法演示
参考链接

四、思考与总结