?

Given an array of integers, every element appears?twice?except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

?

本來是一道非常簡單的題，但是由于加上了時間復雜度必須是O(n)，并且空間復雜度為O(1)，使得不能用排序方法，也不能使用map數(shù)據(jù)結(jié)構(gòu)。那么只能另辟蹊徑，需要用位操作Bit Operation來解此題，這個解法如果讓我想，肯定想不出來，因為誰會想到用邏輯異或來解題呢。邏輯異或的真值表為：

?異或運算的真值表如下：

AB⊕

F	F	F
F	T	T
T	F	T
T	T	F

由于數(shù)字在計算機是以二進制存儲的，每位上都是0或1，如果我們把兩個相同的數(shù)字異或，0與0異或是0,1與1異或也是0，那么我們會得到0。根據(jù)這個特點，我們把數(shù)組中所有的數(shù)字都異或起來，則每對相同的數(shù)字都會得0，然后最后剩下來的數(shù)字就是那個只有1次的數(shù)字。這個方法確實很贊，但是感覺一般人不會忘異或上想，絕對是為CS專業(yè)的同學設計的好題呀，贊一個~~?

?

C++ 解法：

class Solution { public:int singleNumber(vector<int>& nums) {int res = 0;for (auto num : nums) res ^= num;return res;} };

?

Java 解法：

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

?

LeetCode All in One 題目講解匯總(持續(xù)更新中...)

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] Single Number 单独的数字的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。