提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

我们在刷题的时候会碰到各种各样的《只出现一次的数字》的题目，在这里，我们对碰到的题目进行总结

一、给定一个整数数组nums，除了某个元素只出现一次以外，其余元素均出现两次。找出那个只出现一次的元素

异或的性质：

• 0^x = x
• x^x = 0; 同样的数异或两次得到零
• 异或满足交换律和结合律，不需要考虑顺序

由于异或有以上的性质，所以我们可以将数组nums当中的元素依次进行异或操作，此时数组中出现两次的数进行异或后变成了0，而最终异或得到的结果就是只出现一次的那个数

int* singleNumber(int* nums, int numsSize, int* returnSize)
{//找出这个值放到数组int* arr = (int*)malloc(sizeof(int)* 1);//输出型参数，让外面拿到数组的长度*returnSize =1 ;int ret = 0;for (int i = 0; i < numsSize; ++i){ret ^= nums[i];}arr[0] = ret;return arr;
}

二、给你一个整数数组nums，除某个元素仅出现一次外，其余每个元素都恰出现三次。请你找出并返回那个只出现了一次的元素

int类型变量的大小是4个字节，也就是32个比特位。由于相同的数的二进制序列都是一样的，因此当我们遍历nums数组当中的数字，依次同级每个比特位出现1的次数时，就会出现以下几种情况：

• 某一比特位出现1的次数为0，表明数组nums当中的所有数字的该比特位都为0，因此只出现一次的数字的该比特位也为0
• 某一比特位出现1的次数对3取余后得到0值，表明数组nums中只出现一次的数字的该比特位为0
• 某一比特位出现1的次数为3取余后得到非0值，表明数字nums中只出现一次的数字的该比特位为1

因此当我们遍历nums数组统计得到每个比特位出现1的次数之后，就可以将这32个值依次对3进行求余操作，最终得到的32个0/1序列就是只出现一次的数字的二进制序列

#include <stdio.h>
#include <stdlib.h>
int singleNumber(int* nums, int numsSize) 
{int ret = 0; // 初始化结果为0// 遍历整数的32个比特位for (int i = 0; i < 32; i++){int total = 0; // 用于统计当前比特位为1的元素个数// 遍历数组中的所有元素for (int j = 0; j < numsSize; j++) {// 将当前元素右移i位，然后与1进行与操作// 这样可以提取出第i个比特位的值（0或1）total += ((nums[j] >> i) & 1);}// 如果第i个比特位为1的元素个数不能被3整除// 则说明只出现一次的数字的这一比特位为1if (total % 3 != 0){// 使用位或操作将ret的第i个比特位设置为1ret |= (1 << i);}}return ret; // 返回只出现一次的数字
}// 示例使用
int main() {int nums[] = {2, 2, 3, 2}; // 示例数组，3是只出现一次的数字int size = sizeof(nums) / sizeof(nums[0]);int result = singleNumber(nums, size);printf("只出现一次的数字是: %d\n", result); // 应该输出3return 0;
}

我们也可以使用排序后遍历的方法，不过与位操作方法相比，位操作的时间复杂度为O(n)，空间复杂度为O(1)；排序后遍历的方法其复杂度为O(nlongn)，空间复杂度为O(1)或O(n)，但是其实现简单

使用数组排序后遍历

#include <stdio.h>
#include <stdlib.h>// 比较函数，用于qsort
int compare(const void* a, const void* b) {return (*(int*)a - *(int*)b);
}int singleNumber(int* nums, int numsSize) {// 先对数组进行排序qsort(nums, numsSize, sizeof(int), compare);// 遍历排序后的数组for (int i = 0; i < numsSize; i += 3) {// 如果当前元素与下一个元素不同，或者已经到达数组末尾if (i == numsSize - 1 || nums[i] != nums[i + 1]) {return nums[i];}}return -1; // 如果没有找到，返回-1
}

三、一个整型数组nums里除了两个数字之外，其他数字都出现了两次，请找出这两个只出现一次的数字。要求时间复杂度为O(n)，空间复杂度是O(1)

数组nums当中除了出现一次的数字之外，剩下的都是出现两次的数字，但是我们不能直接遍历数组元素进行异或操作，因为此时nums数组当中有两个出现一次的数字，如果我们直接将所有数字进行异或，最终得到的实际就是这两个出现一次的数字相异或后的结果

如果我们可以将数组nums当中的数字分为两组，并且这两个出现一次的数字正好分别分到了两组，此时就相当于分别在这两个小组中找出现一次的数字，问题就回到了第一题

现在的问题就变成了，如何将这两个只出现一次的数字分到两个不同的组别中。
这个实际上很简单，因为我们直接对数组nums当中的元素进行异或操作，得到的实际上就是这两个只出现一次的数字相异或的结果，我们将结果称为ret。由于这两个只出现一次的数字的二进制序列是不同的，因此在ret的二进制序列当中一定至少存在一个不为0的比特位，而这两个只出现一次的数字的该比特位的值是不同的，一个为0，一个为1
因此我们可以根据该比特位来进行分组，将数组nums当中该比特位为1的数字分为一组，将该比特位为0的数字分到另一组，则这两个只出现一次的数字就一定被分到了两个不同的组当中，其他出现两次的数字，要么在这一组，要么在另一组

解题步骤如下：

1. 遍历数组nums，对数组中的所有元素进行异或，得到异或后的结果ret
2. 找出ret当中任意一个不为0的比特位记为j
3. 将原数组分为两组，第j位为1的为a组，第j位为0的为b组
4. x和y一定会分别进入a、b组，其他出现两次的数，要么进入a组，要么进入b组
5. a组和b组数据就变成其他数出现2次，只有一个数出现1次
6. 再对a、b组进行异或就可以找出x和y

int* singleNumber(int* nums, int numsSize, int* returnSize)
{   //1.计算所有元素的异或结果int ret = 0;for (int i = 0; i < numsSize; i++){ret ^= nums[i];}//2.找到ret中为1的任意一位(即x和y不同的位)int j = 0;while (((ret >> j) & 1) == 0){j++;}//3.根据第j位将数组分为两组，并分别计算异或int x = 0, y = 0;for (int k = 0; k < numsSize; k++){if ((nums[k] >> j) & 1){x ^= nums[k];}else{y ^= nums[k];}}//4.准备返回值int* arr = (int*)malloc(sizeof(int)* 2);arr[0] = x;arr[1] = y;*returnSize = 2;return arr;
}

四、给定一个整数数组nums和一个整数k，除了某个元素仅出现一次外，其余每个元素都恰好出现了k次，请你找出并返回那个只出现了一次的元素

数组中除了那个只出现一次的数字之外，无论其他数字出现多少次，我们实际都可以通过统计每个比特位出现1的次数的方式进行求解
只不过现在我们是将得到的32个比特位各自出现1的次数对k进行求余操作，最终得到的32个0/1序列也就是出现一次的数字的二进制序列

#include <stdio.h>
#include <stdlib.h>
int singleNumber(int* nums, int numsSize,int k)
{int ret = 0; // 初始化结果为0// 遍历整数的32个比特位for (int i = 0; i < 32; i++){int total = 0; // 用于统计当前比特位为1的元素个数// 遍历数组中的所有元素for (int j = 0; j < numsSize; j++){// 将当前元素右移i位，然后与1进行与操作// 这样可以提取出第i个比特位的值（0或1）total += ((nums[j] >> i) & 1);}// 如果第i个比特位为1的元素个数不能被k整除// 则说明只出现一次的数字的这一比特位为1if (total % k != 0){// 使用位或操作将ret的第i个比特位设置为1ret |= (1 << i);}}return ret; // 返回只出现一次的数字
}// 示例使用
int main() {int nums[] = { 2, 2, 3, 2 }; // 示例数组，3是只出现一次的数字int size = sizeof(nums) / sizeof(nums[0]);int k = 3;int result = singleNumber(nums, size,k);printf("只出现一次的数字是: %d\n", result); // 应该输出3return 0;
}