題目：

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?

?

看了別人的解答才會的，利用公式a XOR b XOR a = b,從A[n]開始，依次往前執(zhí)行A[n] = A[n] XOR A[n-1],最后A[0]就是答案。

例如如果序列是｛a,b,a,c,b｝

那么數(shù)組A各項(xiàng)分別是：

0	1	2	3	4
c XOR a XOR a = c	c XOR b XOR a XOR b = c XOR a	c XOR b XOR a	c XOR b	b

代碼：

class Solution { public:int singleNumber(int A[], int n) {while(--n){A[n-1] ^= A[n];}return A[0];} };

這里自己還犯了一個(gè)白癡想法，認(rèn)為a XOR b要么是0要么是1，這個(gè)只是對于a，b為0，1的時(shí)候成立的，如果a，b不是0，1，此時(shí)是把a(bǔ)，b表示成二進(jìn)制數(shù)后逐位異或的。

Java版本代碼：

1 public class Solution { 2 public int singleNumber(int[] A) { 3 int answer = 0; 4 for(int i = 0;i < A.length;i++){ 5 answer = answer ^ A[i]; 6 } 7 return answer; 8 } 9 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/sunshineatnoon/p/3636727.html

總結(jié)

以上是生活随笔為你收集整理的【leetcode刷题笔记】Single Number的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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