Generic solution if you do not know about XOR


  • 0
    T

    // although two passes, time is still O(n),
    // better than sort which time is O(nlogn)
    int size = A.size();
    if (size == 0) return 0;
    unordered_map<int, int> hash;
    for (int i = 0; i < size; i++) {
    if ( hash[A[i]] == 0) {
    hash[A[i]]++;
    } else {
    hash[A[i]]--;
    }
    }
    for (int i = 0; i < size; i++) {
    if ( hash[A[i]] == 1) {
    return A[i];
    }
    }


  • 0
    T

    I reply to myself because I do not know how to delete post. I noticed the requirement is to use O(1) space, then my solution is not qualified.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.