力扣刷题之3158.求出出现两次数字的XOR值

题目描述

给你一个数组 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 <= 50
• 1 <= nums[i] <= 50
• nums 中每个数字要么出现过一次，要么出现过两次。

 题干分析

给定一个整数数组 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 64

int 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));  // 输出：1

    int nums2[] = {1, 2, 3};
    int size2 = sizeof(nums2) / sizeof(nums2[0]);
    printf("%d\n", duplicateNumbersXOR(nums2, size2));  // 输出：0

    int nums3[] = {1, 2, 2, 1};
    int size3 = sizeof(nums3) / sizeof(nums3[0]);
    printf("%d\n", duplicateNumbersXOR(nums3, size3));  // 输出：3

    return 0;
}

代码解释

• 计数数组 cnt：定义大小为 MAX_NUM 的计数数组，用于记录每个数字的出现次数。假设输入数组中的元素都不大于 MAX_NUM。
• 结果变量 res：初始化为 0，用于存储最终的 XOR 结果。
• 循环遍历数组：在循环中判断每个数字的出现次数，若为第二次出现，则将其与 res 进行 XOR 运算。

复杂度分析 

• 时间复杂度：O(n)，其中 n 为输入数组的长度。遍历数组的时间复杂度为 O(n)。
• 空间复杂度：O(1)（在 MAX_NUM 为常量的情况下）。使用了固定大小的计数数组。