【本文鏈接】
http://www.cnblogs.com/hellogiser/p/find-n-numbers-which-appear-only-once-in-array.html
【題目】
一個數組中有三個數字a、b、c只出現一次，其他數字都出現了兩次。請找出三個只出現一次的數字。
【分析】
這是一道很新穎的關於位運算的面試題。在之前的博文34.數組中2個只出現一次的數字[Find two numbers which appear once]中分析了N=1和N=2的情況。
(1).N=1時，數組所有數字異或的結果即為a。
(2).N=2時，數組所有數字異或的結果等於a^b，根據a^b的二進制中最後一個1出現的位置，將數組分為2組；對每一組數字進行異或，即可求得a和b。
(3).N=3時，數組所有數字異或的結果等於a^b^c。此時該如何區分呢？如果我們能夠找出其中一個只出現一次的數字，剩下兩個只出現一次的數字就可以轉換為N=2的情況。
具體思路如下：
(1). f(x) = x & (-x)所得的結果即是x最後一位1所在的位置。
(2). x = a ^ b ^ c。
(3). flag = f(x^a)^f(x^b)^f(x^c) 結果必有一位是1，因為f(m)^f(n)結果為0或者為2個1。
(4). f(x^a)^f(x^b)^f(x^c)的第m位為1，則x^a, x^b, x^c必有1個或者3個第m位為1。
(5). 用反證法可得，x^a, x^b, x^c只有一個第m位為1。
舉個例子data={1,2,3,4,4,5,5,6,6}
x = a ^ b ^ c =1^2^3 = 000
x^a=001, x^b=010, x^c=011
f(x^a)=001, f(x^b)=010, f(x^c)=001
flag = f(x^a)^f(x^b)^f(x^c)=010,flag = f(flag)=010
f(x^b)==flag
first=b=1
second=3,third=1
完整代碼如下：
【代碼】
C++ Code
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
// 58_FindNumbersAppearOnce.cpp : Defines the entry point for the console application.
//
/*
version: 1.0
author: hellogiser
blog: http://www.cnblogs.com/hellogiser
date: 2014/5/27
*/
#include "stdafx.h"
// find number which appear once
void Find1NumberAppearOnce(int data[], int length, int &num)
{
if(NULL == data || length < 1)
return;
// get the exclusive or result of array
// a
int xor = 0;
for (int i = 0; i < length; ++i)
xor ^= data[i];
num = xor;
}
// get last 1 bit of n
// n=00001110--->00000010
unsigned int GetLast1Bit(int n)
{
return n & (-n);
}
// find 2 numbers which appear once
void Find2NumbersAppearOnce(int data[], int length, int &num1, int &num2)
{
if(NULL == data || length < 2)
return;
// get the exclusive or result of array
// a^b
int xor = 0;
for (int i = 0; i < length; ++i)
xor ^= data[i];
// find the last bit 1 of xor
int flag = GetLast1Bit(xor);
num1 = num2 = 0;
for(int j = 0; j < length; ++j)
{
// divide numbers in data into 2 groups by flag:
// numbers in group1: the & result is 1
// numbers in group2: the & result is 0
if (flag & data[j])
{
num1 ^= data[j];
}
else
{
num2 ^= data[j];
}
}
}
// swap a and b
void myswap(int &a, int &b)
{
int t = a;
a = b;
b = t;
}
// find 3 numbers which appear once
/*
(1). f(x) = x & (-x)
(2). x = a ^ b ^ c
(3). flag = f(x^a)^f(x^b)^f(x^c)
(4). flag = f(flag)
(5). x^a, x^b, x^c, only one of three is 1 at m-bit
f(x^a)==flag
for example:
data={1,2,3,4,4,5,5,6,6}
x = a ^ b ^ c =1^2^3 = 000
x^a=001, x^b=010, x^c=011
f(x^a)=001, f(x^b)=010, f(x^c)=001
flag = f(x^a)^f(x^b)^f(x^c)=010
flag = f(flag)=010
f(x^b)==flag
first=b=1
second=3,third=1
*/
void Find3NumbersAppearOnce(int data[], int length, int &num1, int &num2, int &num3)
{
if(NULL == data || length < 3)
return;
// get the exclusive or result of array
// a^b^c
int xor = 0;
for(int i = 0; i < length; i++)
xor ^= data[i];
int flag = 0;
for(int i = 0; i < length; i++)
flag ^= GetLast1Bit(xor ^ data[i]);
flag = GetLast1Bit(flag);
// get the first unique number
int first = 0;
for(int i = 0; i < length; i++)
if(GetLast1Bit(data[i] ^ xor) == flag)
first ^= data[i];
num1 = first;
// move the first number to the end of array
for(int i = 0; i < length; i++)
{
if (first == data[i])
{
myswap(data[i], data[length - 1]);
break;
}
}
// get the second and third unique number
Find2NumbersAppearOnce(data, length - 1, num2, num3);
}
//=================================================================
// test cases
void test_base1(int data[], int length)
{
int num1;
Find1NumberAppearOnce(data, length, num1);
printf("%d\n", num1);
}
void test_base2(int data[], int length)
{
int num1, num2;
Find2NumbersAppearOnce(data, length, num1, num2);
printf("%d %d\n", num1, num2);
}
void test_base3(int data[], int length)
{
int num1, num2, num3;
Find3NumbersAppearOnce(data, length, num1, num2, num3);
printf("%d %d %d\n", num1, num2, num3);
}
void test_case1()
{
int data[] = {1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6};
int length = sizeof(data) / sizeof(int);
test_base1(data, length);
}
void test_case2()
{
int data[] = {1, 2, 3, 3, 4, 4, 5, 5, 6, 6};
int length = sizeof(data) / sizeof(int);
test_base2(data, length);
}
void test_case3()
{
int data[] = {1, 2, 3, 4, 4, 5, 5, 6, 6};
int length = sizeof(data) / sizeof(int);
test_base3(data, length);
}
void test_main()
{
test_case1(); // 1
test_case2(); // 1 2
test_case3(); // 2 3 1
}
//=================================================================
int _tmain(int argc, _TCHAR *argv[])
{
test_main();
return 0;
}
【參考】
http://www.cnblogs.com/hellogiser/p/3738909.html
http://zhedahht.blog.163.com/blog/static/25411174201283084246412/
http://www.cnblogs.com/youxin/p/3349834.html
http://www.cnblogs.com/kedebug/archive/2012/12/22/2829013.html
【本文鏈接】
http://www.cnblogs.com/hellogiser/p/find-n-numbers-which-appear-only-once-in-array.html
