LeetCode 3158.求出出现两次数字的 XOR 值：化整数为哈希，一次遍历O(1)空间解决

【LetMeFly】3158.求出出现两次数字的 XOR 值：化整数为哈希，一次遍历O(1)空间解决

力扣题目链接：https://leetcode.cn/problems/find-the-xor-of-numbers-which-appear-twice/

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

请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。

 

示例 1：

输出：1

解释：

nums 中唯一出现过两次的数字是 1 。

示例 2：

输出：0

解释：

nums 中没有数字出现两次。

示例 3：

输出：3

解释：

数字 1 和 2 出现过两次。1 XOR 2 == 3 。

 

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 50
• nums 中每个数字要么出现过一次，要么出现过两次。

解题方法：哈希表

本题中一个数要么出现1次要么出现2次，因此可以使用一个哈希表记录一个数是否出现过。

遍历数组，若一个数出现过，则ans异或之；否则将其加入哈希表中。

因为数据范围是1到50，因此可以使用一个整数的第i位是否为1来表示i是否在哈希表中。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:int duplicateNumbersXOR(vector<int>& nums) {long long ma = 0;int ans = 0;for (int t : nums) {if (ma >> t & 1) {ans ^= t;} else {ma |= 1LL << t;}}return ans;}
};

Go

package mainfunc duplicateNumbersXOR(nums []int) int {ma := int64(0)ans := 0for _, t := range nums {if (ma >> t & 1) > 0 {ans ^= t} else {ma |= int64(1) << t}}return ans
}

Java

class Solution {public int duplicateNumbersXOR(int[] nums) {long ma = 0;int ans = 0;for (int t : nums) {if ((ma >> t & 1) > 0) {ans ^= t;} else {ma ^= (long)(1) << t;}}return ans;}
}

Python

from typing import Listclass Solution:def duplicateNumbersXOR(self, nums: List[int]) -> int:ans = ma = 0for t in nums:if ma >> t & 1:ans ^= telse:ma |= 1 << treturn ans

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/142877697