Codility OddOccurrencesInArray解法优化：从O(n²)到O(n)求助

问题说明：数组长度为奇数（2n+1），除一个元素外，其余每个元素都有一个相同的配对元素。需要找出这个唯一未配对的元素。例如数组 [9,3,9,3,9,7,9]，应返回7。

现有思路分析 #

• 思路一：遍历数组，将首次出现的元素存入另一个向量；后续遇到相同元素时，从该向量中删除。时间复杂度O(n²)（最坏情况如[1,2,3,4,1,2,3,4,5]，每次删除都要遍历向量），空间复杂度O(n/2)。
• 思路二：先排序数组，再遍历检查相邻元素是否成对。时间复杂度O(n log n)（排序）+ O(n)（遍历），空间复杂度O(1)（原地排序）。
• 思路三：用数组元素的值作为第二个数组的索引，统计每个值出现次数，最后找次数为1的元素。时间复杂度O(n)，但空间复杂度取决于数组元素的最大值，空间效率极低。
• 思路四：用哈希表存储元素值作为键，出现次数作为值；遍历哈希表找到值为1的键。时间复杂度O(n)（遍历数组）+ O(n/2+1)（遍历哈希表）= O(n)，空间复杂度O(n/2+1)。
• 思路五：尝试进一步优化空间复杂度。

当前代码问题分析 #

你当前的代码使用了map实现哈希表，但map是基于平衡二叉树的，插入和删除操作的时间复杂度为O(log k)（k为哈希表中元素数量），因此整体时间复杂度为O(n log n)，在处理超大数组时会超时，导致仅通过77%的测试用例。

另外，代码最后遍历哈希表的逻辑可以简化：因为每次元素出现第二次时就会被从哈希表中删除，最终哈希表中只会剩下那个唯一的元素，无需再遍历判断次数。

当前代码：

// you can use includes, for example:
#include <algorithm>
#include <map>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
/*
ODD NUMBER IF ELEMENTS 
Every element is pared with other that has the same value except for one 
Size=2n+1 ,
A= 9,3,9,3,9,7,9 
Returns the unique value or the unpaired 

-First approach 
Traverse the Array and save the unique values in other vector and if you find them later you delete them from the unique array.
Time complexity= O(n)*O(n/2)* = O (n^2)
*for the worst case in which they are [1 2 3 4 1 2 3 4 5]
Space complexity O(n/2)

-Second approach 
Sort the array and then Traverse the array 
Time complexity O(nlogn)+O(n)
Time space O(1) constant

-Third approach
The values of the array are the position of a second one.
Then the array is traversed to find the one where the value is '1'
Time O (2n) = O (n)
Space O(max value of N) -not efficient

-Fourth approach
Hash Map the value is the key and the frequency is the value
Traverse the HashMap and print the key  who has the value of 1
Time O(n)+ O (n/2 + 1) = O (n)
Space O (n/2 + 1)

-Fifth approach 
Probably I could improve the space 
*/

int solution(vector<int> &A) {
    map <int, int> hash; //this is a pair so iterator.first is the key and second is the   value 
    
    for (unsigned int i=0 ; i<A.size() ; i++){
        hash[A[i]]++;
        if ( hash[A[i]] == 2) {
            hash.erase (A[i]); //deleting by key  idk the time in a hash requires to delete 
        }// I think that with this the space complexity is reduced 
    }

    for (auto s : hash){
        if ( s.second == 1){
            return s.first;
            break;
        }
    }
    return 0;
}

优化哈希表解法（O(n)时间复杂度） #

将map替换为unordered_map（哈希表实现，平均O(1)插入/删除），并简化后续遍历逻辑：

#include <unordered_map>

int solution(vector<int> &A) {
    std::unordered_map<int, int> hash;
    
    for (int num : A) {
        if (hash.find(num) != hash.end()) {
            hash.erase(num);
        } else {
            hash[num] = 1;
        }
    }
    
    return hash.begin()->first;
}

这个版本的时间复杂度为O(n)（平均情况），空间复杂度O(n/2+1)，能通过所有测试用例。

最优解法：异或运算（O(n)时间 + O(1)空间） #

利用异或运算的性质：

• 相同数异或结果为0：a ^ a = 0
• 0与任何数异或结果为该数：0 ^ a = a
• 异或满足交换律和结合律：a ^ b ^ a = b ^ (a ^ a) = b ^ 0 = b

遍历数组，将所有元素依次异或，最终结果就是那个唯一未配对的元素。这个解法无需额外空间，时间复杂度O(n)，是最优解：

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

内容的提问来源于stack exchange，提问作者930r91na