lintcode 落单的数（|，||，|||）

（|）
给出2*n + 1 个的数字，除其中一个数字之外其他每个数字均出现两次，找到这个数字。
样例
给出 [1,2,2,1,3,4,3]，返回 4
题目链接：http://www.lintcode.com/zh-cn/problem/single-number/

将数组的数全部做异或，最后得到的数就是要找的数，因为和一个数做两次异或不会改变。

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

（||）
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
样例
给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4
题目链接：http://www.lintcode.com/zh-cn/problem/single-number-ii/#

先将数组排序，依次遍历寻找

class Solution {
public:
    /**
     * @param A : An integer array
     * @return : An integer 
     */
    int singleNumberII(vector<int> &A) {
        // write your code here
        if (A.empty()) return 0;
        sort(A.begin(),A.end());
        int i = 0;
        while (i < A.size()) {
            if (A[i] == A[i + 1] && A[i] == A[i + 2]) i += 3;
            else break;
        }
        return i > A.size() ? A[A.size() - 1] : A[i];
    }
};

(|||)
给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3]，返回 1和5
题目链接：http://www.lintcode.com/zh-cn/problem/single-number-iii/
思路同第二题：

class Solution {
public:
    /**
     * @param A : An integer array
     * @return : Two integers
     */
    vector<int> singleNumberIII(vector<int> &A) {
        // write your code here
        vector<int> res;
        sort(A.begin(), A.end());
        int i = 0;
        while (i < A.size()) {
            if (A[i] == A[i + 1]) i += 2;
            else {
                res.push_back(A[i]);
                i++;
            }
            if (res.size() == 2) break;
        }
        return res;
    }
};

关于第二题和第三题还有一种解法，就是将数组中的数字转换为二进制，网上有较多这种方法，就不赘述了。