leetcode中如何找到只出現一次的數字

這篇文章主要介紹了leetcode中如何找到只出現一次的數字，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創新互聯是一家專注于成都網站制作、網站設計與策劃設計,深州網站建設哪家好?創新互聯做網站,專注于網站建設10多年,網設計領域的專業建站公司;建站業務涵蓋:深州等地區。深州做網站價格咨詢:13518219792

題目鏈接

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

題目描述

給定一個非空整數數組，除了某個元素只出現一次以外，其余每個元素均出現兩次。找出那個只出現了一次的元素。

說明：

你的算法應該具有線性時間復雜度。你可以不使用額外空間來實現嗎？

示例 1:

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

示例 2:

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

解題方案

思路

標簽：位運算
本題根據題意，線性時間復雜度O(n)，很容易想到使用Hash映射來進行計算，遍歷一次后結束得到結果，但是在空間復雜度上會達到O(n)，需要使用較多的額外空間
既滿足時間復雜度又滿足空間復雜度，就要提到位運算中的異或運算XOR，主要因為異或運算有以下幾個特點：

一個數和0做XOR運算等于本身：a⊕0 = a
一個數和其本身做XOR運算等于0：a⊕a = 0
XOR運算滿足交換律和結合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

故而在以上的基礎條件上，將所有數字按照順序做抑或運算，最后剩下的結果即為唯一的數字
時間復雜度：O(n)，空間復雜度：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;
};