《剑指offer》数组中出现次数超过一半的数字-ag真人游戏

题目描述：

  数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

解题思路：

思路一：

数组中有一个数字出现的次数超过数组长度的一半，也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，那么要找的数字肯定是最后一次把次数设为1时对应的数字。

class solution {
public:
    int morethanhalfnum_solution(vector numbers) {
        if(numbers.empty()){
            return 0;
        }
        // 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
        int result = numbers[0];
        int times = 1;
        for(int i = 1; i < numbers.size();   i){
            if(times == 0){
                // 更新result的值为当前元素，并置次数为1
                result = numbers[i];
                times = 1;
            }
            else if(numbers[i] == result){
                times  ;
            }
            else{
                times--;
            }
        }
        // 判断result是否符合条件，即出现次数大于数组长度的一半
        times = 0;
        for(int i = 0; i < numbers.size();   i)
        {
            if(numbers[i] == result){
                times  ;
            }
        }
        return (times > (numbers.size() >> 1)) ? result : 0;
    }
};

思路二：

摩尔投票，这个方法我一开始也想到了，但是没有想到这竟然有理论解释，而且是大名鼎鼎的摩尔投票算法。

它的主要步骤是这样的：

1. 初始化两个变量， cand 表示候选人，cnt 表示赞同它的票数。
2. 如果 cnt = 0，那么 cand 就设置为当前的数字。
3. 如果 cand 等于当前数字，那么票数 cnt 加一，否则票数减一。
4. 最后 cand 就是得票超过一半的众数。

class solution {
public:
    int morethanhalfnum_solution(vector v) {
        int num = v[0], count_i = 1;
        for(int i = 1; i < v.size(); i  ){
            if(v[i] == v[i-1]) count_i  ;
            else {
                if(count_i <= 1) num = v[i];
                else count_i--;
            }
        }
        if (v.size() / 2 < count(v.begin(), v.end(), num)) return num;
        return 0;
    }
};

思路三：

哈希表，这个方法最简单，用哈希表记录每个数字出现的次数，最后看哪个数字次数超过一半就行了。

时间复杂度 o(n) ，空间复杂度 o(n) 。

class solution {
public:
    int majorityelement(vector& nums) {
        int n = nums.size();
        unordered_map mp;
        for (auto x : nums) mp[x]  ;
        for (auto [k, v] : mp) {
            if (v > n/2) return k;
        }
        return 0;
    }
};