[LeetCode]單獨存在的數字(Single Number)

題目描述

給定一個非空的nums整數陣列，除了其中一個元素之外，其它的元素都重複出現了一次。找出單獨存在的那個元素。

您必須實作出線性時間複雜度的解答，且只能夠使用常數的額外空間複雜度。

原題網址

輸入格式

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• 陣列中除了其中一個元素之外，其它的元素都重複出現了一次。

輸出格式

單獨存在的那個整數數字。

範例輸入1

範例輸出1

範例輸入2

範例輸出2

範例輸入3

範例輸出3

題解

這題其實利用#{{A \text{ xor } A = 0}}#和#{{A \text{ xor } 0 = A}}#這兩個邏輯式子就可以解答了。走訪陣列所有的元素，並元素值全都#{{\text{xor}}}#起來，最後的值就是那個單獨存在的元素值。

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {
        nums.into_iter().reduce(|acc, n| acc ^ n).unwrap()
    }
}

const singleNumber = (nums: number[]): number => {
    return nums.reduce((acc, n) => acc ^ n);
};