[Leetcode] 260. Single Number III 解題報告

題目：

Given an array of numbers 

nums

, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given 

nums = [1, 2, 1, 3, 2, 5]

, return 

[3, 5]

.

Note:

1. The order of the result is not important. So in the above example, 

   [5, 3]

    is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

思路：

我們在Leetcode中遇到一個類似的題目，就是說數組中隻有一個數隻出現過一次，其他的都出現了兩次。這道題目的思路和那題一樣，隻是比上一道題目多了一個步驟：首先将所有數都一起異或，得到的結果就是這兩個隻出現一次的數的異或。然後再檢查這個結果的哪一位為1，則說明隻出現一次的兩個數在這一位肯定不相等。然後就可以根據與這個數相與是否為0來将數組分為兩半，則這兩個隻出現一次的數會分别處在兩個不同的數組中。此時問題就回到了原來題目的思路，隻要讓子數組内部元素全部異或一下，得到的兩個數就是最終要的隻出現一次的數。

代碼：

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int tem = 0;
        for (auto val : nums) {
            tem ^= val;
        }
        int lowBit = tem & (-tem);
        vector<int> vec1, vec2;
        for (auto val : nums) {
            if (val & lowBit) {
                vec1.push_back(val);
            }
            else {
                vec2.push_back(val);
            }
        }
        int num1 = 0, num2 = 0;
        for (auto val : vec1) {
            num1 = num1 ^ val;
        }
        for (auto val : vec2) {
            num2 = num2 ^ val;
        }
        return vector<int>{num1, num2};
    }
};