苏州网站建设需要多少钱,北京工商注册流程,上海建网站公司排名,上海本地宝题目内容#xff1a; 在一个数组中#xff0c;室友两个数字出现了一次#xff0c;其他所有数字都出现了两次。找出只出现一次的数字。 如#xff1a;1#xff0c;2#xff0c;3#xff0c;4#xff0c;5#xff0c;1#xff0c;2#xff0c;3#xff0c;4#xff…题目内容 在一个数组中室友两个数字出现了一次其他所有数字都出现了两次。找出只出现一次的数字。 如1234512346 5 和6都只出现了一次找出5和6打印出来 解题思路 这里还是要用到异或运算符 ^来解决。不过和单身狗1不一样的是整个数组异或下来会出现一个别的值是由5^6得到的。这里我们找新得到的值的二进制位的1在哪里。 注意异或运算符是两个数的二进制位对应位相同结果为1不同为0 可以用这点来将两个不同的数字分成两个不同的组然后在分别异或每个组。 1、找出整体异或的结果
int tmp 0;
int i 0;
//将整个数组异或起来得到两个不同数字的异或结果
for (i 0; i n; i)
{tmp ^ arr1[i];
}
2、找到tmp中二进制为1 的某一位k
tmp 可能是 0001 0010 0100所以我们要用到右移运算符
int k 0;
for (i 0; i 32; i)
{if (((tmp i) 1) ! 0){k i;break;}
}
3、将k位上为1的分为一组遍历异或最后的值存储到p1或p2中
* p1 0;
* p2 0;
for (i 0; i n; i)
{if (((arr1[i] k) 1) ! 0){*p1 ^ arr1[i];}else{*p2 arr1[i];}
}
最后来看看完整代码吧
#include stdio.hvoid Fund(int arr1[], int n, int* p1, int* p2)
{int tmp 0;int i 0;//将整个数组异或起来得到两个不同数字的异或结果for (i 0; i n; i){tmp ^ arr1[i];}//2、找到tmp中二进制为1 的某一位kint k 0;for (i 0; i 32; i){if (((tmp i) 1) ! 0){k i;break;}}//3、将k位上为1的分为一组遍历异或最后的值存储到p1或p2中* p1 0;* p2 0;for (i 0; i n; i){if (((arr1[i] k) 1) ! 0){*p1 ^ arr1[i];}else{*p2 arr1[i];}}
}int main()
{int arr[] { 1,2,3,4,5,1,2,3,4,6 };int sz sizeof(arr) / sizeof(arr[0]);int num1 0;int num2 0;Fund(arr, sz, num1, num2);printf(%d %d\n, num1, num2);return 0;
}
结果
