Single Number

Given an array of integers, every element appearstwice except for one. Find that single one.

给出一个整形数组，所有的数字都出现两次，只有一个出现一次。

---

解决方案 1：

思路： 利用 ^ 操作，对于整数x，y来说，x^y = y^x，x ^ x = 0，0^x = x。将数组的所有整数全部做^操作，结果为出现一次的那个数。

代码：

public class Solution {

         public int singleNumber(int[] numbers) {

                  int element = 0;

                  for (int i = 0; i < numbers.length; i++) {

                            element = element ^ numbers[i];

                   }

                 return element;

          }

}

---

解决方案 2：

思路： 

int 型为4字节，32bit，如果将所有数字看作二进制数字，对应的位相加，得bitSum，然后对bitSum取模2，bitSum为出现一次的数字的对应位。得到这个数字的所有位，就可以恢复这个数字。

代码：

public class Solution {

        public int singleNumber(int[] numbers) {

                   int result = 0;

                    for (int i = 0; i  < 32; i++) {

                              int bitSum = 0;

                               for (int j = 0; j < numbers.length; j++) {

                                           bitSum += (numbers[j] >> i) & 1;

                               }

                               result |= (bitSum % 2) << i;

                   }

                    return result;

         }

}

---

总结：

方案一利用了此问题的特殊性，运用异或操作解决问题。

方案二具有一般性，此方法可以扩展为，数组中每个元素出现K次，除了一个元素出现一次的问题形式。