Wednesday, November 13, 2013

[LeetCode] Single Number, Solution

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?

[Thoughts]
不知道这个题从哪里来的,但是明显是针对计算机专业的。很简单,就是位操作,任意两个相同的数如果做异或(Exclusive Or)运算的话,结果为0.所以,这题的解法就是这么直白,从0开始到n,一路异或下去,最后剩下的值就是所求。

[Codes]

1:    int singleNumber(int A[], int n) {  
2:      int left = A[0];  
3:      for(int i =1; i< n; i++)  
4:      {  
5:        left = left ^ A[i];  
6:      }  
7:      return left;  
8:    }  




No comments: