Skip to content

Latest commit

 

History

History
163 lines (125 loc) · 4.44 KB

File metadata and controls

163 lines (125 loc) · 4.44 KB

English Version

题目描述

给你两个下标从 0 开始的数组 nums1 和 nums2 ,两个数组都只包含非负整数。请你求出另外一个数组 nums3 ,包含 nums1 和 nums2 中 所有数对 的异或和(nums1 中每个整数都跟 nums2 中每个整数 恰好 匹配一次)。

请你返回 nums3 中所有整数的 异或和 。

 

示例 1:

输入:nums1 = [2,1,3], nums2 = [10,2,5,0]
输出:13
解释:
一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。
所有这些数字的异或和是 13 ,所以我们返回 13 。

示例 2:

输入:nums1 = [1,2], nums2 = [3,4]
输出:0
解释:
所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ,nums1[0] ^ nums2[1] ,nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。
所以,一个可能的 nums3 数组是 [2,5,1,6] 。
2 ^ 5 ^ 1 ^ 6 = 0 ,所以我们返回 0 。

 

提示:

  • 1 <= nums1.length, nums2.length <= 105
  • 0 <= nums1[i], nums2[j] <= 109

解法

方法一:脑筋急转弯 + 位运算

由于数组的每个元素都会与另一个数组的每个元素进行异或,我们知道,同一个数异或两次,结果不变,即 a ^ a = 0。因此,我们只需要统计数组的长度,就能知道每个元素与另一个数组的每个元素进行异或的次数。

如果 nums2 数组长度为奇数,那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了奇数次异或,因此 nums1 数组的最终异或结果即为 nums1 数组的所有元素异或的结果。如果为偶数,那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了偶数次异或,因此 nums1 数组的最终异或结果为 0。

同理,我们可以得知 nums2 数组的最终异或结果。

最终把两个异或结果再异或一次,即可得到最终结果。

时间复杂度 $O(m+n)$。其中 $m$$n$ 分别为数组 nums1nums2 的长度。

Python3

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        ans = 0
        if len(nums2) & 1:
            for v in nums1:
                ans ^= v
        if len(nums1) & 1:
            for v in nums2:
                ans ^= v
        return ans

Java

class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int ans = 0;
        if (nums2.length % 2 == 1) {
            for (int v : nums1) {
                ans ^= v;
            }
        }
        if (nums1.length % 2 == 1) {
            for (int v : nums2) {
                ans ^= v;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        if (nums2.size() % 2 == 1) {
            for (int v : nums1) {
                ans ^= v;
            }
        }
        if (nums1.size() % 2 == 1) {
            for (int v : nums2) {
                ans ^= v;
            }
        }
        return ans;
    }
};

Go

func xorAllNums(nums1 []int, nums2 []int) int {
	ans := 0
	if len(nums2)%2 == 1 {
		for _, v := range nums1 {
			ans ^= v
		}
	}
	if len(nums1)%2 == 1 {
		for _, v := range nums2 {
			ans ^= v
		}
	}
	return ans
}

TypeScript

function xorAllNums(nums1: number[], nums2: number[]): number {
    let ans = 0;
    if (nums2.length % 2 != 0) {
        ans ^= nums1.reduce((a, c) => a ^ c, 0);
    }
    if (nums1.length % 2 != 0) {
        ans ^= nums2.reduce((a, c) => a ^ c, 0);
    }
    return ans;
}

...