Leetcode: Single Number

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?

Analysis: 需求里面要求O(N)时间以及无额外空间，这就排除了使用boolean array, hashmap这些个方法，只能在原数组上进行查找。O(N)基本上就相当于遍历数组.

最好的方法：

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

第二遍做法： 17行 & 运算符优先等级低于 == 所以一定要打括号

 1 public class Solution {
 2     public int singleNumber(int[] A) {
 3         int[] check = new int[32];
 4         int res = 0;
 5         for (int i=0; i<A.length; i++) {
 6             for (int j=0; j<32; j++) {
 7                 if ((A[i]>>j & 1) == 1) {
 8                     check[j]++;
 9                 }
10             }
11         }
12         for (int k=0; k<32; k++) {
13             if (check[k] % 2 == 1) {
14                 res |= 1<<k;
15             }
16         }
17         return res;
18     }
19 }

一样的思路另一个做法：

 1 public int singleNumber(int[] A) {
 2     int[] digits = new int[32];
 3     for(int i=0;i<32;i++)
 4     {
 5         for(int j=0;j<A.length;j++)
 6         {
 7             digits[i] += (A[j]>>i)&1;
 8         }
 9     }
10     int res = 0;
11     for(int i=0;i<32;i++)
12     {
13         res += (digits[i]%2)<<i;
14     }
15     return res;
16 }

另外注意位运算符的优先级等级：

() [] .

从左到右

! +(正) -(负) ~ ++ --

从右向左

* / %

从左向右

+(加) -(减)

从左向右

<< >> >>>

从左向右

< <= > >= instanceof

从左向右

== !=

从左向右

&(按位与)

从左向右

从右向左

= += -= *= /= %= &= |= ^= ~= <<= >>= >>>=

从右向左