如何降低查找数组中出现奇数次元素的函数时间复杂度？

原代码的性能问题 #

你的代码时间复杂度是O(n²)——外层循环遍历每个元素，内层又完整遍历数组统计次数，再加上维护二维数组B的额外循环，这种嵌套循环在数组规模较大时会导致性能急剧下降，这就是你性能得分仅25%的原因。

最优解法：利用异或运算特性 #

异或运算的几个关键特性刚好适配这个问题：

• 相同数字异或结果为0：x ^ x = 0
• 0和任何数字异或结果为该数字本身：x ^ 0 = x
• 异或运算满足交换律和结合律

基于这些特性，我们只需要遍历数组一次，将所有元素依次异或，最终得到的结果就是那个出现奇数次的元素——出现偶数次的元素会两两异或抵消为0，剩下的就是唯一的目标元素。

优化后代码 #

int solution(vector<int> &A)
{
    int result = 0;
    for (int num : A) {
        result ^= num;
    }
    return result;
}

这个解法的时间复杂度是O(n)，空间复杂度是O(1)，是该问题的最优解，完全能满足面试的性能要求。

备选解法：哈希表统计次数 #

如果对异或特性不熟悉，也可以用哈希表统计每个元素的出现次数，再遍历哈希表找出次数为奇数的元素：

代码示例 #

#include <unordered_map>

int solution(vector<int> &A)
{
    unordered_map<int, int> countMap;
    for (int num : A) {
        countMap[num]++;
    }
    for (const auto& entry : countMap) {
        if (entry.second % 2 != 0) {
            return entry.first;
        }
    }
    return 0; // 题目保证存在目标元素，此返回仅为语法完整性
}

这个解法时间复杂度为O(n)，空间复杂度为O(n)，性能也远优于原代码，但空间消耗比异或解法高。

内容的提问来源于stack exchange，提问作者Salma Ahmed Abdo