1879. Minimum XOR Sum of Two Arrays


题目

题目链接,https://leetcode.com/problems/minimum-xor-sum-of-two-arrays/

You are given two integer arrays nums1 and nums2 of length n.

The XOR sum of the two integer arrays is (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + ... + (nums1[n - 1] XOR nums2[n - 1]) (0-indexed).

  • For example, the XOR sum of [1,2,3] and [3,2,1] is equal to (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4.

Rearrange the elements of nums2 such that the resulting XOR sum is minimized.

Return the XOR sum after the rearrangement.

Example 1:

Input: nums1 = [1,2], nums2 = [2,3]
Output: 2
Explanation: Rearrange nums2 so that it becomes [3,2].
The XOR sum is (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2.

Example 2:

Input: nums1 = [1,0,3], nums2 = [5,3,4]
Output: 8
Explanation: Rearrange nums2 so that it becomes [5,4,3]. 
The XOR sum is (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8.

Constraints:

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <= 14
  • 0 <= nums1[i], nums2[i] <= 107

思路

题目大意是给定等长数组nums1和nums2,重新排列nums2,使得sum(nums1[0] ^ nums2[0] + nums1[1] ^ nums2[1] + ….. + nums1[-1] ^ nums2[-1])最小。

题目里的运算方式是xor,我们知道,xor运算的性质和大小其实没有太大关系;这道题的数量级又略大(n<=14),基本排除了暴力搜索的可能,所以这道题只能记忆化搜索或者动归。

题目提示了可以使用bitmask,我们就顺着这个思路推导下动规的递推方程。

dp[mask] = num2中下标在mask为1的元素与num1的异或值之和的最小值。

于是我们有如下的递推关系

dp[0] = 0

dp[mask] = min(nums1[mask_1_cnt – 1] ^ nums2[i] + dp(mask & ~(1 << i))) , 其中mask_1_cnt为mask中1的个数,i为mask中1的位数。

这里稍微展开一下,为什么num1的下标要取mask_1_cnt – 1,而不是遍历range(1, len(nums))呢——当然可以,但是如果遍历1~len(nums) – 1,我们就需要另外一个状态来记录nums1使用过哪些元素了,时间空间复杂度都会大上几个数量级(n*2n->n2*22n)。

——递推关系是否足够简洁很重要,直接决定了代码会不会TLE或者MLE。

代码

我比较喜欢自顶向下的写法,这里贴一下。

需要注意的是,python里的位运算优先级比四则运算低(详情见链接),所以做位运算的时候一定注意加括号。

时间复杂度为O(n * 2n)

class Solution(object):
    def minimumXORSum(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        
        N = len(nums1)
        
        def count_bit(bits):
            s = bin(bits)
            return len([i for i in s if i == '1'])

        
        l = [None] * (1 << len(nums1))
        l[0] = 0
        def dp(bits):
            if l[bits] is not None:
                return l[bits]
            ret = None
            idx = count_bit(bits) - 1
            for i in range(len(nums1)):
                if (1 << i) & bits == 0:
                    continue
                cur_ans = (nums1[idx] ^ nums2[i]) + dp(bits & ~(1 << i))
                ret = cur_ans if ret is None else min(cur_ans, ret)
            l[bits] = ret
            return ret
            
            
        return dp((1 << len(nums1)) - 1)

提交上去,AC。收工!

等等,还没完。

神仙代码

翻了翻这道题的提交记录,发现python2的第一名居然只有三行,这是什么鬼?必须要贴一下这个代码。

from scipy.optimize import linear_sum_assignment as LSA

class Solution(object):
    def minimumXORSum(self, nums1, nums2):
        cost = [[x^y for y in nums2] for x in nums1]
        return sum(cost[x][y] for x,y in zip(*LSA(cost)))

翻了翻文档,才搞明白,linear_sum_assignment是scipy里的指派问题api,使用的算法为匈牙利算法,时间复杂度O(n3)。参考链接见文末。

本地跑一下,简直快的不像话。

当然weekly contest想必不能这么搞就是了……

姿势水平提高了!

参考链接

1.scipy中的linear_sum_assignment,https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linear_sum_assignment.html#scipy.optimize.linear_sum_assignment

2.匈牙利算法,维基百科,https://zh.m.wikipedia.org/zh-hans/%E5%8C%88%E7%89%99%E5%88%A9%E7%AE%97%E6%B3%95

3.任务分配问题,维基百科,https://zh.m.wikipedia.org/zh-hans/%E4%BB%BB%E5%8A%A1%E5%88%86%E9%85%8D%E9%97%AE%E9%A2%98



——此处是内容的分割线——

除非注明,否则均为广陌原创文章,转载必须以链接形式标明本文链接

本文链接:https://www.utopiafar.com/2022/07/07/leetcode-1879-minimum-xor-sum-of-two-arrays/

码字不易,如果觉得内容有帮助,欢迎留言or点赞!


发表回复

您的电子邮箱地址不会被公开。