題目鏈接

https://leetcode-cn.com/problems/single-number/

題目描述

給定一個(gè)非空整數(shù)數(shù)組，除了某個(gè)元素只出現(xiàn)一次以外，其余每個(gè)元素均出現(xiàn)兩次。找出那個(gè)只出現(xiàn)了一次的元素。

說明：

你的算法應(yīng)該具有線性時(shí)間復(fù)雜度。 你可以不使用額外空間來實(shí)現(xiàn)嗎？

示例 1:

輸入: [2,2,1]
輸出: 1

示例 2:

輸入: [4,1,2,1,2]
輸出: 4

解題方案

思路

• 標(biāo)簽：位運(yùn)算

• 本題根據(jù)題意，線性時(shí)間復(fù)雜度O(n)，很容易想到使用Hash映射來進(jìn)行計(jì)算，遍歷一次后結(jié)束得到結(jié)果，但是在空間復(fù)雜度上會(huì)達(dá)到O(n)，需要使用較多的額外空間

• 既滿足時(shí)間復(fù)雜度又滿足空間復(fù)雜度，就要提到位運(yùn)算中的異或運(yùn)算XOR，主要因?yàn)楫惢蜻\(yùn)算有以下幾個(gè)特點(diǎn)：

• 一個(gè)數(shù)和0做XOR運(yùn)算等于本身：a⊕0 = a

• 一個(gè)數(shù)和其本身做XOR運(yùn)算等于0：a⊕a = 0

• XOR運(yùn)算滿足交換律和結(jié)合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

• 故而在以上的基礎(chǔ)條件上，將所有數(shù)字按照順序做抑或運(yùn)算，最后剩下的結(jié)果即為唯一的數(shù)字

• 時(shí)間復(fù)雜度：O(n)，空間復(fù)雜度：O(1)

代碼

• Java版本

class Solution {
   public int singleNumber(int[] nums) {
       int ans = 0;
       for(int num: nums) {
           ans ^= num;
       }
       return ans;
   }
}

• JavaScript版本

/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
   let ans = 0;
   for(const num of nums) {
       ans ^= num;
   }
   return ans;
};

畫解