数组中只出现一次的两个数字

浏览数：17 / 时间：2015年06月08日

题目：给定一个整型数组，其中有两个数字只出现一次，其余的数字都出现两次，找出这两个只出现一次的数字．时间复杂度为Ｏ(n)，空间复杂度为O(1)．

异或运算的特性：相等的两个整数异或的结果为０；一个整数与０进行异或运算的结果为其本身．

基本思想：将这两个只出现一次的数字分到两个数组中，这样就很容易找到只出现一次的数字．

采用上述思想需要解决的问题：

１．如何才能保证两个只出现一次的数字分别位于两个数组？

２．空间复杂度为Ｏ(1)，需要在原数组上进行分割操作，这个如何做到？

解决办法：

１．将数组中的所有数字进行异或运算，得到一个非零值．然后找出这个非零值的二进制形式中１第一次出现的位置．根据得到的这个位置的值是否为１将数组分成两个部分．可以得知，两个只出现一次的数字将被分到不同的部分．

２．快速排序的patition函数可以很好地解决这个问题．以某一标准将数组分成两个不同的部分．

代码如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 void get_num(int *, int);
 6 void swap(int *, int *);
 7 
 8 int main(int argc, char *argv[])
 9 {
10     int a[14] = {1, 2, 5, 1, 5, 2, 16, 20, 23, 20, 16, 30, 23, 6};
11     int result = 0;
12 
13     get_num(a, sizeof(a)/sizeof(int));
14 
15     return 0;
16 }
17 
18 void get_num(int *a, int len)
19 {
20     int result = 0;
21     int result1 = 0;
22     int result2 = 0;
23     int m = 0;
24     int i = 0;
25     int j = 0;
26     int p = 0;
27 
28     for (i=0; i<len; i++)
29     {
30         printf("%d ", *(a + i));
31         result = *(a + i) ^ result;
32     }
33     printf("\n");
34 
35     while (m < 32)
36     {
37         if (result % 2 != 0)
38         {
39             break;            
40         }
41 
42         result = result >> 1;
43         m++;
44     }
45     printf("m = %d\n", m);
46     i = -1;
47     j = 0;
48     for (j=0; j<len; j++)
49     {
50         if ((*(a + j) >> m) % 2 != 0)
51         {
52             swap((a + i + 1), (a + j));
53             i++;
54         }
55     }
56 
57     p = i;
58     for (i=0; i<=p; i++)
59     {
60         printf("%d ", *(a + i));
61         result1 = *(a + i) ^ result1;
62     }
63     printf("\n");
64 
65     for (i=p+1; i<len; i++)
66     {
67         printf("%d ", *(a + i));
68         result2 = *(a + i) ^ result2;
69     }
70     printf("\n");
71     
72     printf("%d  %d\n", result1, result2);
73 
74 }
75 
76 
77 void swap(int *a, int *b)
78 {
79     int temp;
80     temp = *a;
81     *a = *b;
82     *b = temp;
83 }