LeetCode多数元素题解遇内存超限及遍历错误求助

错误原因分析 #

你的代码出现内存超限的核心问题是哈希表遍历逻辑错误：

• 用for(int i = 0;i<hash.size();i++)遍历哈希表时，访问hash[i]会触发unordered_map的特性：如果键i不存在，会自动插入一个键为i、值为0的元素。
• 这会导致hash.size()在循环中不断增大，循环条件i < hash.size()永远成立，形成死循环，哈希表持续扩张最终耗尽内存。
• 同时，你错误地把循环变量i当成数组元素的值来判断，完全偏离了需求——哈希表的键是原数组的元素，不是从0开始的索引。

修正后的哈希表解法 #

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> hash; // 无需用long long，数组元素类型为int
        int n = nums.size();
        // 统计每个元素出现次数
        for (int num : nums) {
            hash[num]++;
        }
        // 遍历哈希表找符合条件的元素
        for (auto& pair : hash) {
            if (pair.second > n / 2) {
                return pair.first;
            }
        }
        return -1; // 题目保证存在多数元素，此代码不会执行
    }
};

更优解法：摩尔投票法 #

由于题目明确多数元素存在，可使用空间复杂度O(1)的摩尔投票法，无需额外哈希表：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 1;
        for (int i = 1; i < nums.size(); ++i) {
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            } else if (nums[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }
        return candidate;
    }
};

内容的提问来源于stack exchange，提问作者Bhavya Jain