1879. 两个数组最小的异或值之和
大约 4 分钟
---
1879. 两个数组最小的异或值之和
- 标签:位运算、数组、动态规划、状态压缩
- 难度:困难
题目链接
题目大意
描述:给定两个整数数组 和 ,两个数组长度都为 。
要求:将 中的元素重新排列,使得两个数组的异或值之和最小。并返回重新排列之后的异或值之和。
说明:
- 两个数组的异或值之和:(下标从 开始)。
- 举个例子, 和 的异或值之和 等于 。
- 。
- 。
- 。
- 。
示例:
- 示例 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。
解题思路
思路 1:状态压缩 DP
由于数组 可以重新排列,所以我们可以将数组 中的元素顺序固定,然后将数组 中第 个元素与数组 中所有还没被选择的元素进行组合,找到异或值之和最小的组合。
同时因为两个数组长度 的大小范围只有 ,所以我们可以采用「状态压缩」的方式来表示 中当前元素的选择情况。
「状态压缩」指的是使用一个 位的二进制数 来表示排列中数的选取情况。
如果二进制数 的第 位为 ,说明数组 第 个元素在该状态中被选取。反之,如果该二进制的第 位为 ,说明数组 中第 个元素在该状态中没有被选取。
举个例子:
- ,,表示选择了第 个元素和第 个元素,也就是 、。
- ,,表示选择了第 个元素、第 个元素、第 个元素,也就是 、、。
这样,我们就可以通过动态规划的方式来解决这道题。
1. 划分阶段
按照数组 中元素选择情况进行阶段划分。
2. 定义状态
定义当前数组 中元素选择状态为 , 对应选择的元素个数为 。
则可以定义状态 表示为:当前数组 中元素选择状态为 ,并且选择了 中前 个元素的情况下,可以组成的最小异或值之和。
3. 状态转移方程
对于当前状态 ,肯定是从比 少选一个元素的状态中递推而来。我们可以枚举少选一个元素的状态,找到可以组成的异或值之和最小值,赋值给 。
举个例子 ,,表示选择了第 个元素和第 个元素,也就是 、。那么 只能从 和 这两个状态转移而来,我们只需要枚举这两种状态,并求出转移过来的异或值之和最小值。
即状态转移方程为:,其中 第 位一定为 , 为 中 的个数。
4. 初始条件
- 既然是求最小值,不妨将所有状态初始为最大值。
- 未选择任何数时,异或值之和为 ,所以初始化 。
5. 最终结果
根据我们之前定义的状态, 表示为:当前数组 中元素选择状态为 ,并且选择了 中前 个元素的情况下,可以组成的最小异或值之和。 所以最终结果为 ,其中 。
思路 1:代码
class Solution:
def minimumXORSum(self, nums1: List[int], nums2: List[int]) -> int:
ans = float('inf')
size = len(nums1)
states = 1 << size
dp = [float('inf') for _ in range(states)]
dp[0] = 0
for state in range(states):
one_cnt = bin(state).count('1')
for i in range(size):
if (state >> i) & 1:
dp[state] = min(dp[state], dp[state ^ (1 << i)] + (nums1[i] ^ nums2[one_cnt - 1]))
return dp[states - 1]
思路 1:复杂度分析
- 时间复杂度:,其中 是数组 、 的长度。
- 空间复杂度:。