【剑指Offer学习】【面试题40:数组中只出现一次的数字】
程序员文章站
2022-07-15 10:44:20
...
题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次,请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
https://cuijiahua.com/blog/2018/01/basis_40.html
bool isBitOne(int num,int index) {
return (num>>index)%2 == 1;
}
bool diffTwo(int a[],int len, int *one,int *two) {
if (NULL == a || len <=0) {
return false;
}
int ret = a[0];
for (int i = 1; i<len; i++) {
ret = ret ^ a[i];
}
int k = 0;
while (ret%2 != 1) {
ret = ret / 2;
k++;
}
for (int j = 0; j<len; j++) {
if (isBitOne(a[j],k)) {
*one = *one ^ a[j];
}
else {
*two = *two ^ a[j];
}
}
return true;
}
推荐阅读
-
剑指 offer代码最优解析——面试题35第一个只出现一次的字符
-
剑指offer 56 数组中数字出现的次数 lintcode 82. 落单的数、83. 落单的数 II、84. 落单的数 III
-
【剑指offer】面试题56(1):数组中只出现一次的两个数字
-
剑指offer:数组中只出现一次的两个数字(java版)
-
剑指offer 面试题56 python版+解析:数组中只出现一次的两个数字,数组中唯一只出现一次的数字
-
剑指offer第二版-56.数组中只出现一次的两个数字
-
【算法分享】剑指offer56-数组中只出现一次的两个数字
-
剑指 Offer 56 - I. 数组中只出现一次的两个数字
-
剑指56:数组中只出现一次的数字——异或——位运算
-
《剑指Offer》Java刷题 NO.40 数组中只出现一次的数字(数组、HashMap、位运算、异或)