• 数组中只出现一次的数字
    • 题目
    • 解题思路

    数组中只出现一次的数字

    题目

    牛客网

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

    解题思路

    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. }