面试题 39：数组中出现次数超过一半的数字.md

试题链接：52. 数组中出现次数超过一半的数字 - AcWing题库

方法一：哈希表计数

• 思路：用哈希表记录每个数出现的次数，当某个数的出现次数超过总数量的一半时得到答案。
• 时间复杂度：O(n)
• 空间复杂度：O(n)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> cnt;
        for (int num : nums) {
            cnt[num]++;
            if (cnt[num] > n / 2) return num;
        }
        return -1;
    }
};

方法二：摩尔投票

• 思路：遍历数组并实时维护出现次数最多的数，如果遇到相同的则出现次数加一，否则减一，若减为零则下一个出现的数为最多，通过这种不同的数抵消的方式，最后剩下的数一定是出现次数超过一半的数。
• 时间复杂度：O(n)
• 空间复杂度：O(1)

class Solution {
public:
    int moreThanHalfNum_Solution(vector<int>& nums) {
        int d, cnt = 0;
        
        for (int num : nums) {
            if (cnt == 0) {
                d = num;
                cnt = 1;
            } else if (num == d) {
                cnt++;
            } else {
                cnt--;
            }
        }
        
        return d;
    }
};