c语言找两个只出现了一次的数,其余数出现了两次
时间: 2023-05-28 09:05:47 浏览: 68
题目描述:
给定一个整数数组,其中除了两个数只出现一次外,其余数都出现了两次。找出这两个只出现了一次的数。要求时间复杂度为O(n),空间复杂度为O(1)。
解题思路:
首先可以将所有的数进行异或操作,得到的结果就是两个只出现了一次的数的异或结果。因为两个相同的数进行异或操作的结果为0,所以最后的结果就是两个只出现了一次的数的异或结果。
接下来,我们要分别找出这两个只出现了一次的数。因为这两个数不相同,所以它们的二进制表示中至少有一位是不同的。我们可以根据这一位将原数组分成两个子数组,使得这两个只出现了一次的数分别在不同的子数组中。
接着,对这两个子数组分别进行异或操作,得到的结果就是这两个只出现了一次的数。
代码实现:
```
void findNumsAppearOnce(int* nums, int numsSize, int* num1, int *num2) {
int i, res = 0, flag = 1;
*num1 = 0;
*num2 = 0;
// 所有数进行异或操作
for (i = 0; i < numsSize; i++) {
res ^= nums[i];
}
// 找到两个只出现了一次的数的二进制表示中不同的那一位
while ((res & flag) == 0) {
flag <<= 1;
}
// 根据这一位将原数组分成两个子数组
for (i = 0; i < numsSize; i++) {
if ((nums[i] & flag) == 0) {
*num1 ^= nums[i];
} else {
*num2 ^= nums[i];
}
}
}
```