Single Number

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

http://www.lintcode.com/en/problem/single-number/

Solution

用异或操作，同为0，异为1. 所有数异或，只有出现一次的那个剩下。

class Solution {
public:
    /**
     * @param A: Array of integers.
     * return: The single number.
     */
    int singleNumber(vector<int> &A) {
        // write your code here
        int result = 0;
        for(int i=0; i<n; i++) {
            result ^= A[i];
        }
        return result;
    }
};

位操作太难想了，常规思路呢？把每个元素出现的次数存到个hash里。

class Solution {
public:
    /**
     * @param A: Array of integers.
     * return: The single number.
     */
    int singleNumber(vector<int> &A) {
        // write your code here
        int n = A.size();
        if (n==0) return 0;
        unordered_map<int, int> mymap;
        for(int i=0; i<n; i++) {
            if(mymap.find(A[i]) != mymap.end()) {
                mymap[A[i]] = 2;
            } else {
                mymap[A[i]] = 1;
            }
        }
        for(int i=0; i<n; i++) {
            if(mymap[A[i]] == 1)
                return A[i];
        }
    }
};