网站与备案信息不符,如何建设网站兴田德润怎么样,正能量网站入口直接进入下载,160 作者 网站建设 amp一个数组中只有两个数字是出现一次#xff0c;其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。 例如#xff1a;有数组的元素是#xff1a;1,2,3,4,5,1,2,3,4,6#xff0c;只有5和6只出现1次#xff0c;要找出5和6。 这里我们不妨回忆一下之前找单身… 一个数组中只有两个数字是出现一次其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。 例如有数组的元素是1,2,3,4,5,1,2,3,4,6只有5和6只出现1次要找出5和6。 这里我们不妨回忆一下之前找单身狗1的思想找单身狗1
这次数组里有两个单身狗那么如果我们能把这个数组分成两组每组都有一个单身狗再按照找单身狗1的思想这样不就可以找到这两个单身狗了吗Yes
那么问题来了我们怎么把这两只单身狗分到两组中去呢
我们不妨先把数组中的全部元素异或1^2^3^4^5^1^2^3^4^65^65^6的二进制结果是 这样我们发现倒数第一位和倒数第二位的结果为1原因是由于5和6二进制的倒数第一位和倒数第二位相异那么不妨只考虑倒数第一个相异为1的那一位即倒数第一位考虑倒数第二个相异为1的那一位也可通过判断倒数第一位是0还是1把数组元素分成两类。把数组元素分成两类后就可以按照单身狗1的做法就可以找出这两个单身狗了
代码如下:
#include stdio.h
int find_single_dog2(int arr[], int sz,int* pr1,int* pr2)
{int n 0;int i 0;//1.所有元素异或到一起for (i 0; i sz; i){n ^ arr[i];}//2.计算n的第几位是1得到iint pos 0;for (i 0; i 32; i){if (((n i) 1) 1){pos i;//记录所有元素异或后第一个1的位置根据这个位置是1还是0将数组元素分为两组break;}}//3.分组for (i 0; i sz; i){if (((arr[i] pos) 1) 1){*pr1 ^ arr[i];}else{*pr2 ^ arr[i];}}}
int main()
{int arr[] { 1,2,3,4,5,1,2,3,4,6 };int ret1 0;int ret2 0;int sz sizeof(arr) / sizeof(arr[0]);find_single_dog2(arr, sz, ret1, ret2);printf(单身狗是%d和%d\n, ret1, ret2);return 0;
}
