溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹了leetcode中如何找到只出現(xiàn)一次的數(shù)字，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。
https://leetcode-cn.com/problems/single-number/
給定一個非空整數(shù)數(shù)組，除了某個元素只出現(xiàn)一次以外，其余每個元素均出現(xiàn)兩次。找出那個只出現(xiàn)了一次的元素。
說明：
你的算法應該具有線性時間復雜度。 你可以不使用額外空間來實現(xiàn)嗎？
示例 1:
輸入: [2,2,1]
輸出: 1
示例 2:
輸入: [4,1,2,1,2]
輸出: 4
標簽：位運算
本題根據(jù)題意，線性時間復雜度O(n)，很容易想到使用Hash映射來進行計算，遍歷一次后結束得到結果，但是在空間復雜度上會達到O(n)，需要使用較多的額外空間
既滿足時間復雜度又滿足空間復雜度，就要提到位運算中的異或運算XOR，主要因為異或運算有以下幾個特點：
一個數(shù)和0做XOR運算等于本身：a⊕0 = a
一個數(shù)和其本身做XOR運算等于0：a⊕a = 0
XOR運算滿足交換律和結合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b
故而在以上的基礎條件上，將所有數(shù)字按照順序做抑或運算，最后剩下的結果即為唯一的數(shù)字
時間復雜度：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;
};
感謝你能夠認真閱讀完這篇文章，希望小編分享的“l(fā)eetcode中如何找到只出現(xiàn)一次的數(shù)字”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業(yè)資訊頻道，更多相關知識等著你來學習!
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權內容。
