Hard

题目描述

给定两个长度为 n 的整数数组 nums1 和 nums2。

两个整数数组的异或和定义为 (nums1[0] XOR nums2[0]) + (nums1[1] XOR nums2[1]) + … + (nums1[n - 1] XOR nums2[n - 1])（下标从 0 开始）。

例如，[1,2,3] 和 [3,2,1] 的异或和等于 (1 XOR 3) + (2 XOR 2) + (3 XOR 1) = 2 + 0 + 2 = 4。

重新排列 nums2 中的元素，使得异或和最小。

返回重新排列后的异或和。

示例 1：

输入：nums1 = [1,2], nums2 = [2,3]
输出：2
解释：重新排列 nums2，使其变为 [3,2]。
异或和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 2。

示例 2：

输入：nums1 = [1,0,3], nums2 = [5,3,4]
输出：8
解释：重新排列 nums2，使其变为 [5,4,3]。
异或和为 (1 XOR 5) + (0 XOR 4) + (3 XOR 3) = 4 + 4 + 0 = 8。

约束条件：

  • n == nums1.length
  • n == nums2.length
  • 1 <= n <= 14
  • 0 <= nums1[i], nums2[i] <= 10^7

解题思路

这是一个经典的状态压缩动态规划问题。由于 n ≤ 14，我们可以使用位掩码来表示 nums2 中已经使用过的元素。

核心思路：

状态压缩 DP 的关键是定义状态。我们用 dp[mask] 表示当使用了 nums2 中由 mask 表示的元素集合时，能达到的最小异或和。

具体来说：

  • mask 的第 i 位为 1 表示 nums2[i] 已被使用
  • dp[mask] 对应处理了 nums1 的前 popcount(mask) 个元素

状态转移： 对于状态 mask，假设已经处理了 nums1 的前 k 个元素（k = popcount(mask)），现在要处理第 k 个元素 nums1[k]。我们枚举 nums2 中未使用的元素 nums2[j]，即 mask 的第 j 位为 0 的位置。

转移方程：dp[mask | (1 << j)] = min(dp[mask | (1 << j)], dp[mask] + (nums1[k] ^ nums2[j]))

算法流程：

  1. 初始化 dp 数组，dp[0] = 0
  2. 枚举所有状态 mask
  3. 对于每个 mask，计算当前处理到 nums1 的第几个元素
  4. 枚举 nums2 中未使用的元素进行转移
  5. 最终答案为 dp[(1 « n) - 1]

时间复杂度为 O(2^n × n)，由于 n ≤ 14，完全可以接受。

代码实现

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        vector<int> dp(1 << n, INT_MAX);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == INT_MAX) continue;
            int k = __builtin_popcount(mask);
            if (k == n) continue;
            
            for (int j = 0; j < n; j++) {
                if (!(mask & (1 << j))) {
                    int newMask = mask | (1 << j);
                    dp[newMask] = min(dp[newMask], dp[mask] + (nums1[k] ^ nums2[j]));
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
};

class Solution:
    def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        dp = [float('inf')] * (1 << n)
        dp[0] = 0
        
        for mask in range(1 << n):
            if dp[mask] == float('inf'):
                continue
            k = bin(mask).count('1')
            if k == n:
                continue
                
            for j in range(n):
                if not (mask & (1 << j)):
                    new_mask = mask | (1 << j)
                    dp[new_mask] = min(dp[new_mask], dp[mask] + (nums1[k] ^ nums2[j]))
        
        return dp[(1 << n) - 1]

public class Solution {
    public int MinimumXORSum(int[] nums1, int[] nums2) {
        int n = nums1.Length;
        int[] dp = new int[1 << n];
        Array.Fill(dp, int.MaxValue);
        dp[0] = 0;
        
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == int.MaxValue) continue;
            int k = System.Numerics.BitOperations.PopCount((uint)mask);
            if (k == n) continue;
            
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) == 0) {
                    int newMask = mask | (1 << j);
                    dp[newMask] = Math.Min(dp[newMask], dp[mask] + (nums1[k] ^ nums2[j]));
                }
            }
        }
        
        return dp[(1 << n) - 1];
    }
}

var minimumXORSum = function(nums1, nums2) {
    const n = nums1.length;
    const dp = new Array(1 << n).fill(Infinity);
    dp[0] = 0;
    
    for (let mask = 0; mask < (1 << n); mask++) {
        if (dp[mask]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(2^n × n) - 需要遍历所有 2^n 个状态，每个状态需要 O(n) 时间进行转移
空间复杂度O(2^n) - dp 数组需要存储 2^n 个状态的值

相关题目