Single Number II

转自：http://blog.csdn.net/kenden23/article/details/13625297

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

时间复杂度O(n*n)

这类题目排序都是可以做的，先排序，再扫描，时间复杂度O(nlgn)

 1     int singleNumber(int A[], int n) {
 2         if(A==NULL||n<=0)
 3             return 0;
 4         sort(A,A+n);
 5         int i;
 6         for(i=0;i<n-2;++i)
 7         {
 8             if(A[i]==A[i+1]&&A[i]==A[i+2])
 9                 i+=3;
10             else
11                 return A[i];
12         }
13     }

Submission Result: Wrong Answer

Input:	[1]
Output:	-256
Expected:	1

 1     int singleNumber(int A[], int n) {
 2         if(A==NULL||n<=0)
 3             return 0;
 4         if(n<=2)
 5             return A[0];
 6         sort(A,A+n);
 7         int i;
 8         for(i=0;i<n-2;++i)
 9         {
10             if(A[i]==A[i+1]&&A[i]==A[i+2])
11                 i+=3;
12             else
13                 return A[i];
14         }
15     }

Status: Wrong Answer

Input:	[2,2,3,2]
Output:	0
Expected:	3

根据错误提示分析：

n=4 i=0

排序后：2，2，2，3

A[0]=A[1]=A[2]

i=3

i<n-2——>3<2不成立，然后呢，就木有然后了

 1     int singleNumber(int A[], int n) {
 2         if(A==NULL||n<=0)
 3             return 0;
 4         //if(n<=2)
 5             //return A[0];
 6         sort(A,A+n);
 7         int i=0;
 8         while(i<n-2)
 9         {
10             if(A[i]==A[i+1]&&A[i]==A[i+2])
11                 i+=3;
12             else
13                 break;
14         }
15         return A[i];
16     }

PS:现在发现用for越来越不顺手了，下面有个i+=3，然后for里有个习惯性的++i，然后就出错了······

O(n)的解法：http://www.cnblogs.com/daijinqiao/p/3352893.html

对于除出现一次之外的所有的整数，其二进制表示中每一位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。

上面那句话说的太好啦，赞一个，可惜代码没看懂

http://www.cppblog.com/Uriel/articles/205406.html

我自己写的，错的，错在14行

 1     int singleNumber(int A[], int n) {
 2         if(A==NULL||n<=0)
 3             return 0;
 4         int i,j,bit,result=0;//bit记录所有数某一位加起来mod3之后每位是0还是1
 5         int b=1;//b用来取得数的某一位
 6         //unsigned int b=1;
 7         for(i=0;i<32;i++)//int有32位，虽然是双重循环，但时间复杂度是O(n)
 8         {
 9             bit=0;
10             for(j=0;j<n;++j)
11             {
12                 bit+=(b&A[j]);
13             }
14             //bit%=3;//可以放心地说余数只会是0或者1  //呃，这里错了，以为这里一次只有一位，其实不是的哇
15             result |= bit;
16             b<<1;
17         }//每次循环得到一位，循环结束做或操作
18         return result;
19     }

 1     int singleNumber(int A[], int n) {
 2         if(A==NULL||n<=0)
 3             return 0;
 4         int i,j,result=0;
 5         int b=1;//b用来取得数的某一位
 6         //unsigned int b=1;  两个都可以
 7         int count;//记录所有数某一位加起
 8         for(i=0;i<32;i++)//int有32位，虽然是双重循环，但时间复杂度是O(n)
 9         {
10             count=0;
11             for(j=0;j<n;++j)
12             {
13                 if(b&A[j])
14                     count++;
15             }
16             count%=3;//余数只可能是0或者1
17             if(count)
18                 result |= b;
19             b<<1;
20         }//每次循环得到一位，循环结束做或操作
21         return result;
22     }

Submission Result: Wrong Answer

Input:	[2,2,3,2]
Output:	1
Expected:	3

哪里错啦，思路那么清晰，后来我把代码放到codeblocks中，人家提示说：E:yxycodeblocksdfasdsadsmain.cpp|24|warning: statement has no effect [-Wunused-value]|　　　　　　注：codeblocks中的24行对应上面代码的19行

后来，把第19行改成了b=b<<1;就AC啦，唉，如果是b+1，那我知道没有用，b值不变，b<<1也是类似哇