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 main

func duplicateNumbersXOR(nums []int) int {
    ma := int64(0)
    ans := 0
    for _, 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 List

class Solution:
    def duplicateNumbersXOR(self, nums: List[int]) -> int:
        ans = ma = 0
        for t in nums:
            if ma >> t & 1:
                ans ^= t
            else:
                ma |= 1 << t
        return ans

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

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

原文地址：https://blog.csdn.net/Tisfy/article/details/142877697

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！