大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > C++技巧 > 数组中N(n=1,2,3)个只出现一次的数字

数组中N(n=1,2,3)个只出现一次的数字

关键词:数组C++  阅读(848) 赞(10)

[摘要]本文是对数组中N(n=1,2,3)个只出现一次的数字的讲解,对学习C++编程技术有所帮助,与大家分享。
【题目】

一个数组中有三个数字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:Definestheentrypointfortheconsoleapplication.
//
/*
version:1.0
author:hellogiser
blog:http://www.cnblogs.com/hellogiser
date:2014/5/27
*/

#include"stdafx.h"

//findnumberwhichappearonce
voidFind1NumberAppearOnce(intdata[],intlength,int&num)
{
if(NULL==data||length<1)
return;

//gettheexclusiveorresultofarray
//a
intxor=0;
for(inti=0;i<length;++i)
xor^=data[i];
num=xor;
}

//getlast1bitofn
//n=00001110--->00000010
unsignedintGetLast1Bit(intn)
{
returnn&(-n);
}

//find2numberswhichappearonce
voidFind2NumbersAppearOnce(intdata[],intlength,int&num1,int&num2)
{
if(NULL==data||length<2)
return;

//gettheexclusiveorresultofarray
//a^b
intxor=0;
for(inti=0;i<length;++i)
xor^=data[i];

//findthelastbit1ofxor
intflag=GetLast1Bit(xor);
num1=num2=0;
for(intj=0;j<length;++j)
{
//dividenumbersindatainto2groupsbyflag:
//numbersingroup1:the&resultis1
//numbersingroup2:the&resultis0
if(flag&data[j])
{
num1^=data[j];
}
else
{
num2^=data[j];
}
}
}

//swapaandb
voidmyswap(int&a,int&b)
{
intt=a;
a=b;
b=t;
}

//find3numberswhichappearonce
/*
(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,onlyoneofthreeis1atm-bit
f(x^a)==flag

forexample:
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
*/
voidFind3NumbersAppearOnce(intdata[],intlength,int&num1,int&num2,int&num3)
{
if(NULL==data||length<3)
return;

//gettheexclusiveorresultofarray
//a^b^c
intxor=0;
for(inti=0;i<length;i++)
xor^=data[i];

intflag=0;
for(inti=0;i<length;i++)
flag^=GetLast1Bit(xor^data[i]);
flag=GetLast1Bit(flag);

//getthefirstuniquenumber
intfirst=0;
for(inti=0;i<length;i++)
if(GetLast1Bit(data[i]^xor)==flag)
first^=data[i];
num1=first;

//movethefirstnumbertotheendofarray
for(inti=0;i<length;i++)
{
if(first==data[i])
{
myswap(data[i],data[length-1]);
break;
}
}

//getthesecondandthirduniquenumber
Find2NumbersAppearOnce(data,length-1,num2,num3);
}

//=================================================================
//testcases
voidtest_base1(intdata[],intlength)
{
intnum1;
Find1NumberAppearOnce(data,length,num1);
printf("%d\n",num1);
}

voidtest_base2(intdata[],intlength)
{
intnum1,num2;
Find2NumbersAppearOnce(data,length,num1,num2);
printf("%d%d\n",num1,num2);
}

voidtest_base3(intdata[],intlength)
{
intnum1,num2,num3;
Find3NumbersAppearOnce(data,length,num1,num2,num3);
printf("%d%d%d\n",num1,num2,num3);
}

voidtest_case1()
{
intdata[]={1,2,2,3,3,4,4,5,5,6,6};
intlength=sizeof(data)/sizeof(int);
test_base1(data,length);
}

voidtest_case2()
{
intdata[]={1,2,3,3,4,4,5,5,6,6};
intlength=sizeof(data)/sizeof(int);
test_base2(data,length);
}

voidtest_case3()
{
intdata[]={1,2,3,4,4,5,5,6,6};
intlength=sizeof(data)/sizeof(int);
test_base3(data,length);
}

voidtest_main()
{
test_case1();//1
test_case2();//12
test_case3();//231
}
//=================================================================

int_tmain(intargc,_TCHAR*argv[])
{
test_main();
return0;
}


相关评论