leetcode筆記：Single Number

leetcode筆記：Single Number

一.題目描述

二.解題思路

題目提到，一個數組中除了一個數只出現一次之外，其他數都出現了兩次，找出這個特別的數。

這道題對時間和空間有要求，面對這種情況，一般是暗示有十分輕巧而簡便的方法進行求解。在一些場景下，使用基本的邏輯運算是個不錯的選擇。自己簡單寫了一下，再參照網上部分解法，基本都是使用了異或運算(XOR)，任何數與自己進行按位異或都等於0，而任何數與0進行按位異或都等於本身。

在C/C++中，按位異或運算符為：“^”

基於以上規則，我們可以將整個數組的元素都按位進行異或，最終返回那個只出現一次的數了。

三.示例代碼

// 時間復雜度O(n)，空間復雜度O(1)
class Solution {
public:
    int FindSingleNumber(int A[], int n) 
    {
        int x = 0;
        for (size_t i = 0; i < n; ++i)
        x ^= A[i];  // XOR
        return x;
    }
};

四.總結

本題使用了bool運算中的異或，除此之外沒有大的難點，不知是否有更高效的算法。

因為使用到了異或，結合網上相關博文的總結，在這記錄一下異或運算的性質和常見用法，其實這些性質很容易驗證：

一個數和自己做異或的結果是0；
和0做異或保持原值不變，和1做異或得到原值的相反值；
如果a1^a2^a3^…^an的結果為1，則表示a1到an之中1的個數為奇數，否則為偶數。這一性質可用於奇偶校驗；
x^x^y == y，推導很簡單：x^x == 0，而 0^y == y。這一性質可用於在不允許使用中間變量來交換兩個數的情況下，實現兩個數的交換，如以下swap函數，交換a和b的值：

void swap(int &a,int &b)
{
    a ^= b;
    b ^= a;
    a ^= b;
}

然而，該辦法並不是沒有漏洞。如果輸入a和b的值相等，得到的結果就不是我們想要的，原因如下：

a ^= a;
a ^= a;
a ^= a;

對自身異或結果自然是0了。

因此，將數值交換函數改成以下形式，可避免這種錯誤發生：

void swap(int &a,int &b)
{
    if(a == b) return; // 防止&a，&b指向同一個地址
    a ^= b;
    b ^= a;
    a ^= b;
}