题目描述
给你一个数组 nums ，数组中的数字 要么 出现一次，要么 出现两次。
请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。
示例 1：
输入：nums = [1,2,1,3]
输出：1
解释：
nums 中唯一出现过两次的数字是 1 。
示例 2：
输入：nums = [1,2,3]
输出：0
解释：
nums 中没有数字出现两次。
示例 3：
输入：nums = [1,2,2,1]
输出：3
解释：
数字 1 和 2 出现过两次。1 XOR 2 == 3 。
提示：
1 <= nums.length <= 501 <= nums[i] <= 50nums中每个数字要么出现过一次，要么出现过两次。
题干分析
给定一个整数数组 nums，数组中的数字要么出现一次，要么出现两次。要求返回数组中所有出现两次的数字的按位 XOR 值。如果没有数字出现两次，返回 0。
示例：
-
输入：
nums = [1, 2, 1, 3]
输出：1
解释：nums中唯一出现过两次的数字是1。 -
输入：
nums = [1, 2, 3]
输出：0
解释：nums中没有数字出现两次。 -
输入：
nums = [1, 2, 2, 1]
输出：3
解释：数字1和2出现过两次。1 XOR 2 == 3。
解题思路
1.使用技术数组
- 本题中需要找出所有出现两次的数字的按位XOR值。可以通过使用一个技术数组cnt来跟踪每个数字在数组中出现的次数。
2.遍历数组
- 对数组进行遍历，记录每个数字出现的次数
- 如果该元素已经出现一次（即cnt[nums[i]] == 1），将该元素的值与结果res进行按位XOR运算。
- 如果该元素是第一次出现，则将其标记成出现一次。
3.最后返回结果res，即所有出现两次数字的按位XOR值。
解题步骤
- 初始化计数数组
cnt，大小为MAX_NUM，用于记录每个数字的出现次数。 - 初始化结果变量
res为0。 - 遍历输入数组
nums，对每个元素进行以下操作：- 如果该元素已经出现过一次，则将其与结果变量
res进行按位 XOR 运算。 - 否则，将该元素的出现次数设置为
1。
- 如果该元素已经出现过一次，则将其与结果变量
- 返回结果变量
res，即为所有出现两次数字的按位 XOR 值。
代码实现
#include <stdio.h>
#define MAX_NUM 64int duplicateNumbersXOR(int* nums, int numsSize) {int cnt[MAX_NUM] = {0};int res = 0;for (int i = 0; i < numsSize; ++i) {if (cnt[nums[i]] == 1) {res ^= nums[i];} else {cnt[nums[i]] = 1;}}return res;
}int main() {int nums1[] = {1, 2, 1, 3};int size1 = sizeof(nums1) / sizeof(nums1[0]);printf("%d\n", duplicateNumbersXOR(nums1, size1)); // 输出：1int nums2[] = {1, 2, 3};int size2 = sizeof(nums2) / sizeof(nums2[0]);printf("%d\n", duplicateNumbersXOR(nums2, size2)); // 输出：0int nums3[] = {1, 2, 2, 1};int size3 = sizeof(nums3) / sizeof(nums3[0]);printf("%d\n", duplicateNumbersXOR(nums3, size3)); // 输出：3return 0;
}
代码解释
- 计数数组
cnt：定义大小为MAX_NUM的计数数组，用于记录每个数字的出现次数。假设输入数组中的元素都不大于MAX_NUM。 - 结果变量
res：初始化为0，用于存储最终的 XOR 结果。 - 循环遍历数组：在循环中判断每个数字的出现次数，若为第二次出现，则将其与
res进行 XOR 运算。
复杂度分析
- 时间复杂度：
O(n)，其中n为输入数组的长度。遍历数组的时间复杂度为O(n)。 - 空间复杂度：
O(1)（在MAX_NUM为常量的情况下）。使用了固定大小的计数数组。