数列L中有n个整数,其中K个数字出现了两次,1个数字出现了一次,所以n=2k+1;请在使用O(1)空间的前提下,尽快找出只出现一次的那个数字,并说明算法的复杂度。
既然是空间复杂度的限制
所以
int res = 0;\
for( int i = 0; i \< n; i++ ){\
res \^= arr[i];\
}\
return res;
最终有
1.两个相同的数异或结果为0
2.0与任何数异或结果还是这个数
变种:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
\#include "stdafx.h"\
\
// Find first bit of iValue beginning with right side of iValue.\
int FindFirstBit( int iValue ){\
int iPos = 0;\
while( !(iValue \>\> iPos & 0x1) )\
iPos++;\
return iPos;\
}\
\
inline bool IsBitOne( int iValue, int iPos ){\
return (iValue \>\> iPos) & 0x1;\
}\
\
void FindSingleTwoElem( int arr[], int n, int \*elem1, int \*elem2 ){\
assert( elem1 != NULL && elem2 != NULL );\
\
int orData = 0;\
for( int i = 0; i \< n; i++ )\
orData \^= arr[i];\
\
int iPos = FindFirstBit( orData );\
\
\*elem1 = 0;\
\*elem2 = 0;\
for( int i = 0; i \< n; i++ )\
{\
if( IsBitOne( arr[i], iPos ) )\
\*elem1 \^= arr[i];\
else\
\*elem2 \^= arr[i];\
}\
}\
\
int main(){\
int arr[10]={1,2,3,4,5,6,4,3,2,1};\
int elem1, elem2;\
FindSingleTwoElem( arr, 10, &elem1, &elem2 );\
cout \<\< elem1 \<\< " " \<\< elem2 \<\< endl;\
}
\