C语言编程实现: 给你一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现 两次。 找出只出现一次的那两个元素。你可以按任意顺序返回答案。
时间: 2024-01-30 21:36:23 浏览: 96
数组中只出现一次的两个数字.md
思路:
1. 将所有元素进行异或操作,得到的结果即为两个只出现一次的元素的异或结果。
2. 由于两个只出现一次的元素不相同,因此它们在二进制下必定存在不同的位,也就是说,在这些不同的位上,一个元素的对应位是 0,另一个元素的对应位是 1。
3. 根据异或的性质,对于任意一个数 x,都有 x ^ x = 0,x ^ 0 = x,因此将数组中所有元素分成两组,一组对应位为 0,另一组对应位为 1。这样,只出现一次的两个元素就被分配到了不同的组中。
4. 对于每一组,再分别对所有元素进行异或操作,得到的结果就是只出现一次的那个元素。
代码实现:
```
void singleNumber(int* nums, int numsSize, int* returnSize){
int diff = 0;
for (int i = 0; i < numsSize; i++) {
diff ^= nums[i];
}
// 找到不同的位
int mask = 1;
while ((mask & diff) == 0) {
mask <<= 1;
}
int a = 0, b = 0;
for (int i = 0; i < numsSize; i++) {
if (nums[i] & mask) {
a ^= nums[i];
} else {
b ^= nums[i];
}
}
int* res = (int*)malloc(sizeof(int) * 2);
res[0] = a;
res[1] = b;
*returnSize = 2;
return res;
}
```
阅读全文