Posted on 2014-01-16 03:19
Uriel 阅读(93)
评论(0) 编辑 收藏 引用 所属分类:
LeetCode
给一堆数,其中只有一个只出现过1次,其他都出现2次,找出那个出现1次的,其实是简单位运算,但是就没往位运算上想,还在纠结怎么可能空间复杂度O(1),看了解题报告恍然大悟:
http://www.cnblogs.com/feiling/p/3349654.html就是不断做异或运算就好,最后剩下的就是只出现了1次的那个数
1 class Solution {
2 public:
3 int singleNumber(int A[], int n) {
4 int tp = 0;
5 if(!n) return 0;
6 for(int i = 0; i < n; ++i) {
7 tp = tp ^ A[i];
8 }
9 return tp;
10 }
11 };