九度OJ 1351 数组中只出现一次的数字

时间:2022-10-05 19:34:10

题目地址:http://ac.jobdu.com/problem.php?pid=1351

题目描述:
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
输入:
每个测试案例包括两行:
第一行包含一个整数n,表示数组大小。2<=n <= 10^6。
第二行包含n个整数,表示数组元素,元素均为int。
输出:
对应每个测试案例,输出数组中只出现一次的两个数。输出的数字从小到大的顺序。
样例输入:
8
2 4 3 6 3 2 5 5
样例输出:
4 6
#include <stdio.h>

unsigned int FindFirstBitIs1 (int num){
int indexBit = 0; while ((num & 1) == 0 && indexBit < 32){
num >>= 1;
++indexBit;
}
return indexBit;
} int IsBit1 (int data, unsigned int indexof1){
data >>= indexof1;
return data & 0x01;
} void FindNumsAppearOnce (int data[], int n, int * num1, int * num2){
int result = 0;
int i; for (i=0; i<n; ++i){
result ^= data[i];
}
unsigned int indexof1 = FindFirstBitIs1 (result);
*num1 = 0;
*num2 = 0;
for (i=0; i<n; ++i){
if (IsBit1 (data[i], indexof1))
*num1 ^= data[i];
else
*num2 ^= data[i];
}
} int main(void){
int n;
int input[1000000];
int i;
int num1;
int num2; while (scanf ("%d", &n) != EOF){
for (i=0; i<n; ++i)
scanf ("%d", &input[i]);
FindNumsAppearOnce (input, n, &num1, &num2);
if (num1 < num2)
printf ("%d %d\n", num1, num2);
else
printf ("%d %d\n", num2, num1);
} return 0;
}

参考资料:何海涛 -- 程序员面试题精选100题(34)-数组中只出现一次的数字[算法]