By yusijia

Updated:

Contents

在一个数组中除两个数字只出现1次外，其它数字都出现了2次， 要求尽快找出这两个数字。

  • 两个相同的数异或结果为0，
  • 任何一个数与0异或结果还是那个数,

  • 异或-1相当于取反

    设题目中这两个只出现1次的数字分别为A和B，如果能将A，B分开到二个数组中，那显然符合“异或”解法的关键点了。因此这个题目的关键点就是将A，B分开到二个数组中。由于A，B肯定是不相等的，因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A，B分开到A组和B组。而这个数组中其它数字要么就属于A组，要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A，B了。而要判断A，B在哪一位上不相同，只要根据A异或B的结果就可以知道了，这个结果在二进制上为1的位都说明A，B在这一位上是不相同的。
    比如int a[] = {1, 1, 3, 5, 2, 2}
    整个数组异或的结果为3^5即 0x0011 ^ 0x0101 = 0x0110
    对0x0110，第1位（由低向高，从0开始）就是1。因此整个数组根据第1位是0还是1分成两组。
    a[0] =1 0x0001 第一组
    a[1] =1 0x0001 第一组
    a[2] =3 0x0011 第二组
    a[3] =5 0x0101 第一组
    a[4] =2 0x0010 第二组
    a[5] =2 0x0010 第二组
    第一组有{1, 1, 5}，第二组有{3, 2, 3}，明显对这二组分别执行“异或”解法就可以得到5和3了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>

using namespace std;

void FindTwoNotRepeatNumberInArray(int arr[], int n, int *p1, int *p2)
{
    int j, temp = 0;
    // 计算所有数的异或结果
    for(int i = 0; i < n; i++){
        temp ^= arr[i];
    }
    // 找从右往左第一个为1的位
    for(j = 0; j < 32; j++){
        if(((temp >> j) & 1) == 1){
            break;
        }
    }

    *p1 = 0, *p2 = 0;
    for(int i = 0; i < n; i++){
        if(((arr[i] >> j) & 1) == 0){// 第一组
            *p1 ^= arr[i];
        }else{// 第二组
            *p2 ^= arr[i];
        }
    }
}

int main()
{
    int result1, result2;
    int a[10] = {1, 2, 3, 4, 1, 2, 3, 4, 0, 5};
    FindTwoNotRepeatNumberInArray(a, 10, &result1, &result2);
    printf("%d %d\n", result1, result2);
    return 0;
}
Contents