数组中只出现一次的数字

题目

牛客网

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

解题思路

  1. 两个相等的数字进行异或的结果为0
  2. 在这个特殊的数组中，重复出现的数字只能为2次，那么如果将所有数字异或 就等价与将两个不同的数字进行异或
  3. 异或的结果肯定有一位为1，那么这两个不同的数字，在这一位上不同。
  4. 找到第一个为1的位，并将第一位为1的位是否为1作为分组条件，相同的数字一定在同一个分组里，整个数组分组异或
  5. 得到两个结果，即为两个不同的数
  1. /**
  2.  * num1,num2分别为长度为1的数组。传出参数。将num1[0],num2[0]设置为返回结果
  3.  * @param array
  4.  * @param num1
  5.  * @param num2
  6.  */
  7. public void FindNumsAppearOnce(int[] array, int num1[], int num2[]) {
  8.     if (array == null || array.length < 3) {
  9.         return;
  10.     }
  12.     int result = array[0];
  14.     for (int i = 1; i < array.length; i++) {
  15.         result ^= array[i];
  16.     }
  18.     //找到第一个为1的位
  19.     int indexOfFirstBit1 = 0;
  20.     int temp = result;
  21.     while (temp != 0) {
  22.         indexOfFirstBit1++;
  23.         temp >>>= 1;
  24.     }
  26.     int mask = 1;
  27.     for (int i = 1; i < indexOfFirstBit1; i++) {
  28.         mask <<= 1;
  29.     }
  31.     //将第一位为1的位是否为1作为分组条件，分组异或
  32.     int n1 = -1, n2 = -1;
  33.     for (int i : array) {
  34.         if ((i & mask) == mask) {
  35.             if (n1 == -1) n1 = i;
  36.             else n1 ^= i;
  37.         } else {
  38.             if (n2 == -1) n2 = i;
  39.             else n2 ^= i;
  40.         }
  41.     }
  43.     num1[0] = n1;
  44.     num2[0] = n2;
  45. }