【leetcode】摩尔投票-229.求众数 & 169.多数元素

【leetcode】摩尔投票-229.求众数 & 169.多数元素

229.求众数
题目：给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

测试用例：
输入：[3,2,3]
输出：[3]

题目分析：这是一个摩尔投票问题。所谓摩尔投票，就像一场大仗，分为两个阵营，若两个阵营都有活着的士兵，则互相厮杀，直至某个阵营完全破灭。而该题目，对于任意一个数组，假设有m个数出现恰好n/3次，那么还剩n-nm/3=(1-m/3)n>=0，那么m<=3，由于要超过n/3次，因此m<3，即m最大为2，也就是任意一个数组，最多只有2个数出现超过n/3次。因此，假设两个变量A和B，并且对这两个变量计数，逐个扫描数组，当A还没有赋值时，则把当前值赋给A，并且countA加1，往后扫描，若当前值不为A并且B还没有赋值时，同理把当前值赋给A，并且countB加1，往后扫描；若当前值与A相等，并且countA不为0（避免恰好当前值为初始值），那么A所在阵营个数+1；同理B；若当前值不与AB相等，那么相当于AB阵营都阵死一个。最终根据countA和countB是否为0，判断当前AB是否有效。而此时得到的AB仅为出现次数最多和次多的，并且countA和countB并不是AB在数组中出现的次数，因此还需要循环一次，求出AB出现的次数，并判断是否大与n/3。

代码：

class Solution {
public:
    vector majorityElement(vector& nums) {
        int A = 0;
        int B = 0;//存放出现次数最多的数
        int countA = 0;
        int countB = 0;
        vector num;
        if(nums.size()<1 || nums.size()>5e4)
        {
            return num;
        }
        else
        {
            for (int i = 0;i0? true:false;
        bool Bm = countB>0? true:false;//表示此时的AB是否有值，避免恰好为0的情况
        countA = 0;
        countB = 0;
        for (int i = 0;inums.size()/3)
        {
            num.push_back(B);
        }
        if(countA>nums.size()/3)
        {
            num.push_back(A);
        }
        return num;
    }
};

执行用时：16 ms, 在所有 C++ 提交中击败了33.82%的用户
内存消耗：15.4 MB, 在所有 C++ 提交中击败了54.37%的用户

相似题目：169.多数元素
题目：给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

题目分析：最多只有一个元素，设为most，并计数。
代码：

在class Solution {
public:
    int majorityElement(vector& nums) {
        int most = 0;
        int count = 0;
        for(int i = 0;inums.size()/2)
        {
            return most;
        }
        else
        {
            return false;
        }
    }
};

执行用时：20 ms, 在所有 C++ 提交中击败了46.82%的用户
内存消耗：19.1 MB, 在所有 C++ 提交中击败了64.07%的用户