Easy

题目描述

给你一个数组 nums，其中数组中的每个数字要么出现一次，要么出现两次。

返回所有出现两次的数字的按位异或结果，如果没有数字出现两次，则返回 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
  • 数组中的每个数字要么出现一次，要么出现两次。

解题思路

这道题要求找出所有出现两次的数字并计算它们的异或值。有几种解法可以考虑：

方法一：哈希表计数（推荐）

最直观的做法是使用哈希表统计每个数字的出现次数，然后将所有出现两次的数字进行异或运算。由于数据规模很小（最多50个元素），这种方法效率很高且思路清晰。

方法二：位运算优化

利用异或运算的性质：相同数字异或为0，0与任何数异或为该数本身。我们可以先对所有数字进行异或，然后减去只出现一次的数字的异或值，但这需要额外的空间来记录出现次数。

方法三：暴力枚举

对于每个数字，遍历整个数组计算其出现次数。虽然时间复杂度较高，但在当前数据规模下完全可行。

考虑到代码简洁性和可读性，推荐使用哈希表方法。先统计频次，再对频次为2的数字进行异或运算。

代码实现

class Solution {
public:
    int duplicateNumbersXOR(vector<int>& nums) {
        unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        
        int result = 0;
        for (auto& pair : count) {
            if (pair.second == 2) {
                result ^= pair.first;
            }
        }
        
        return result;
    }
};

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        count = {}
        for num in nums:
            count[num] = count.get(num, 0) + 1
        
        result = 0
        for num, freq in count.items():
            if freq == 2:
                result ^= num
        
        return result

public class Solution {
    public int DuplicateNumbersXOR(int[] nums) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (count.ContainsKey(num)) {
                count[num]++;
            } else {
                count[num] = 1;
            }
        }
        
        int result = 0;
        foreach (var pair in count) {
            if (pair.Value == 2) {
                result ^= pair.Key;
            }
        }
        
        return result;
    }
}

var duplicateNumbersXOR = function(nums) {
    const count = {};
    let result = 0;
    
    for (let num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    
    for (let num in count) {
        if (count[num] === 2) {
            result ^= parseInt(num);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(k)

其中 n 是数组长度，k 是不同数字的个数（最多为 n）。

相关题目