题目描述

给你两个整数数组 nums1 和 nums2，它们长度都为 n。

两个数组的 异或值之和 为
(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 中的元素重新排列，使得 异或值之和 最小。

请你返回重新排列之后的 异或值之和。

样例

输入：nums1 = [1,2], nums2 = [2,3]
输出：2
解释：将 nums2 重新排列得到 [3,2]。
异或值之和为 (1 XOR 3) + (2 XOR 2) = 2 + 0 = 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

算法

(状态压缩动态规划) $O(n \cdot 2^n)$

1. 设状态 $f(S)$ 表示使用了 $nums2$ 数组中下标集合为 $S$ 的数字时的最小异或值之和。
2. 初始时，$f(0) = 0$ 其余为正无穷。
3. 转移时，对于 $f(S)$，首先确定 $S$ 状态表示此次匹配到了 $nums1$ 中的下标位置（$S$ 二进制中 $1$ 的个数） $cnt$。然后，假如 $S$ 在第 $i$ 位为 $1$，则可以转移 $f(S) = \min(f(S), f(S - 2^i) + nums1(cnt - 1) \text{ XOR } nums2(i))$。
4. 最终答案为 $f(2^n - 1)$。

时间复杂度

• 状态数为 $O(2^n)$，每个状态的转移时间为 $O(n)$，故总时间复杂度为 $O(n \cdot 2^n)$。

空间复杂度

• 需要 $O(2^n)$ 的额外空间存储状态。

C++ 代码

class Solution {
public:
    int minimumXORSum(vector<int>& nums1, vector<int>& nums2) {
        const int n = nums1.size();
        vector<int> f(1 << n, INT_MAX);

        f[0] = 0;

        for (int s = 1; s < (1 << n); s++) {
            int cnt = 0;
            for (int i = 0; i < n; i++)
                if (s & (1 << i))
                    cnt++;

            for (int i = 0; i < n; i++)
                if (s & (1 << i))
                    f[s] = min(f[s], f[s ^ (1 << i)] + (nums1[cnt - 1] ^ nums2[i]));
        }

        return f[(1 << n) - 1];
    }
};