Medium

题目描述

给你一个整数数组 nums 和一个整数 target。

你可以从 nums 中移除任意数量的元素（可能为零）。

返回使剩余元素的按位异或等于 target 所需的最少移除次数。如果无法达到 target，则返回 -1。

空数组的按位异或为 0。

示例 1：

输入：nums = [1,2,3], target = 2
输出：1
解释：
移除 nums[1] = 2 后剩余 [nums[0], nums[2]] = [1, 3]。
[1, 3] 的异或为 2，等于目标值。
无法用少于一次移除来达到异或值 2，因此答案是 1。

示例 2：

输入：nums = [2,4], target = 1
输出：-1
解释：
无法通过移除元素来达到目标值。因此答案是 -1。

示例 3：

输入：nums = [7], target = 7
输出：0
解释：
所有元素的异或值为 nums[0] = 7，等于目标值。因此不需要移除。

约束：

  • 1 <= nums.length <= 40
  • 0 <= nums[i] <= 10^4
  • 0 <= target <= 10^4

提示：

  • 使用折半查找或动态规划

解题思路

这是一个典型的子集异或问题。我们需要找到一个子集，使得其异或值等于目标值，并且这个子集包含的元素最多（即移除的元素最少）。

方法一：动态规划 我们可以使用动态规划来解决这个问题。定义 dp[xor] 为达到异或值 xor 所需的最多元素数量。对于每个元素，我们有两个选择：选择它或不选择它。

方法二：折半查找（推荐） 由于数组长度最大为40，如果使用暴力枚举所有子集会有 2^40 种可能，时间复杂度过高。我们可以使用折半查找的思想：

  1. 将数组分成两半
  2. 对前一半枚举所有可能的子集异或值，记录每个异或值对应的最大元素数量
  3. 对后一半枚举所有可能的子集异或值，对于每个异或值 xor2，查找前一半是否存在 xor1 使得 xor1 ^ xor2 = target
  4. 如果存在，更新答案为数组长度减去最大元素数量

这种方法将时间复杂度降低到 O(2^(n/2))，在 n=40 的情况下是可以接受的。

代码实现

class Solution {
public:
    int minRemovals(vector<int>& nums, int target) {
        int n = nums.size();
        int mid = n / 2;
        
        // 处理前半部分
        unordered_map<int, int> firstHalf;
        for (int mask = 0; mask < (1 << mid); mask++) {
            int xorVal = 0;
            int count = 0;
            for (int i = 0; i < mid; i++) {
                if (mask & (1 << i)) {
                    xorVal ^= nums[i];
                    count++;
                }
            }
            firstHalf[xorVal] = max(firstHalf[xorVal], count);
        }
        
        int maxElements = -1;
        
        // 处理后半部分
        for (int mask = 0; mask < (1 << (n - mid)); mask++) {
            int xorVal = 0;
            int count = 0;
            for (int i = 0; i < n - mid; i++) {
                if (mask & (1 << i)) {
                    xorVal ^= nums[mid + i];
                    count++;
                }
            }
            
            int needed = target ^ xorVal;
            if (firstHalf.find(needed) != firstHalf.end()) {
                maxElements = max(maxElements, count + firstHalf[needed]);
            }
        }
        
        return maxElements == -1 ? -1 : n - maxElements;
    }
};

class Solution:
    def minRemovals(self, nums: List[int], target: int) -> int:
        n = len(nums)
        mid = n // 2
        
        # 处理前半部分
        first_half = {}
        for mask in range(1 << mid):
            xor_val = 0
            count = 0
            for i in range(mid):
                if mask & (1 << i):
                    xor_val ^= nums[i]
                    count += 1
            first_half[xor_val] = max(first_half.get(xor_val, 0), count)
        
        max_elements = -1
        
        # 处理后半部分
        for mask in range(1 << (n - mid)):
            xor_val = 0
            count = 0
            for i in range(n - mid):
                if mask & (1 << i):
                    xor_val ^= nums[mid + i]
                    count += 1
            
            needed = target ^ xor_val
            if needed in first_half:
                max_elements = max(max_elements, count + first_half[needed])
        
        return -1 if max_elements == -1 else n - max_elements

public class Solution {
    public int MinRemovals(int[] nums, int target) {
        int n = nums.Length;
        int mid = n / 2;
        
        // 处理前半部分
        var firstHalf = new Dictionary<int, int>();
        for (int mask = 0; mask < (1 << mid); mask++) {
            int xorVal = 0;
            int count = 0;
            for (int i = 0; i < mid; i++) {
                if ((mask & (1 << i)) != 0) {
                    xorVal ^= nums[i];
                    count++;
                }
            }
            firstHalf[xorVal] = Math.Max(firstHalf.GetValueOrDefault(xorVal, 0), count);
        }
        
        int maxElements = -1;
        
        // 处理后半部分
        for (int mask = 0; mask < (1 << (n - mid)); mask++) {
            int xorVal = 0;
            int count = 0;
            for (int i = 0; i < n - mid; i++) {
                if ((mask & (1 << i)) != 0) {
                    xorVal ^= nums[mid + i];
                    count++;
                }
            }
            
            int needed = target ^ xorVal;
            if (firstHalf.ContainsKey(needed)) {
                maxElements = Math.Max(maxElements, count + firstHalf[needed]);
            }
        }
        
        return maxElements == -1 ? -1 : n - maxElements;
    }
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var minRemovals = function(nums, target) {
    const n = nums.length;
    let maxKeep = -1;
    
    // Try all possible subsets
    for (let mask = 0; mask < (1 << n); mask++) {
        let xor = 0;
        let count = 0;
        
        for (let i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                xor ^= nums[i];
                count++;
            }
        }
        
        if (xor === target) {
            maxKeep = Math.max(maxKeep, count);
        }
    }
    
    return maxKeep === -1 ? -1 : n - maxKeep;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(2^(n/2) * n)
空间复杂度O(2^(n/2))

其中 n 是数组长度。折半查找将指数复杂度从 O(2^n) 优化到 O(2^(n/2))，在 n=40 时从约 10^12 降到约 10^6，大大提高了效率。