2997. 使数组异或等于 K 的最少操作次数

Medium

题目描述

给你一个下标从 0 开始的整数数组 nums 和一个正整数 k。

你可以对数组执行下述操作 任意次：

• 选择数组的任一元素，并 翻转 其二进制表示中的一个比特位。翻转比特位意味着将 0 变为 1，或者将 1 变为 0。

返回使数组元素按位异或结果等于 k 所需的 最少 操作次数。

注意，你可以翻转元素二进制表示中的前导零。例如，对于数字 (101)₂，你可以翻转第四个比特位，得到 (1101)₂。

示例 1：

输入：nums = [2,1,3,4], k = 1
输出：2
解释：我们可以执行以下操作：
- 选择元素 2，即 3 == (011)₂，翻转第一个比特位得到 (010)₂ == 2，nums 变为 [2,1,2,4]。
- 选择元素 0，即 2 == (010)₂，翻转第三个比特位得到 (110)₂ == 6，nums 变为 [6,1,2,4]。
最终数组的按位异或结果是 (6 XOR 1 XOR 2 XOR 4) == 1 == k。
可以证明我们无法用少于 2 次操作使按位异或结果等于 k。

示例 2：

输入：nums = [2,0,2,0], k = 0
输出：0
解释：数组的按位异或结果是 (2 XOR 0 XOR 2 XOR 0) == 0 == k，因此不需要执行任何操作。

提示：

• 1 <= nums.length <= 10⁵
• 0 <= nums[i] <= 10⁶
• 0 <= k <= 10⁶

解题思路

这道题的核心思想是利用异或运算的性质来分析问题。

首先理解题目要求：我们需要通过翻转数组中任意元素的任意比特位，使得所有元素的异或结果等于目标值 k。

关键洞察：

1. 当前数组所有元素的异或结果记为 currentXor
2. 我们需要将 currentXor 变为 k
3. 异或运算有一个重要性质：a XOR b XOR b = a，即任何数与自身异或结果为0

解题思路：

1. 计算当前数组所有元素的异或值 currentXor
2. 计算 currentXor XOR k，这个值表示需要"修正"的位
3. 统计 currentXor XOR k 中有多少个1，每个1表示需要翻转一个比特位
4. 由于我们可以选择任意元素的任意位进行翻转，所以答案就是不同位的数量

为什么这样有效？

• 如果 currentXor 的第 i 位与 k 的第 i 位不同，我们需要翻转某个元素的第 i 位
• 翻转任意一个元素的第 i 位都会改变整体异或结果的第 i 位
• 因此每个不同的位都需要恰好一次翻转操作

这种方法时间复杂度为 O(n + log(max(nums, k)))，空间复杂度为 O(1)。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        int currentXor = 0;
        for (int num : nums) {
            currentXor ^= num;
        }
        
        int diff = currentXor ^ k;
        return __builtin_popcount(diff);
    }
};

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        current_xor = 0
        for num in nums:
            current_xor ^= num
        
        diff = current_xor ^ k
        return bin(diff).count('1')

public class Solution {
    public int MinOperations(int[] nums, int k) {
        int currentXor = 0;
        foreach (int num in nums) {
            currentXor ^= num;
        }
        
        int diff = currentXor ^ k;
        return System.Numerics.BitOperations.PopCount((uint)diff);
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minOperations = function(nums, k) {
    let currentXor = 0;
    for (let num of nums) {
        currentXor ^= num;
    }
    
    let diff = currentXor ^ k;
    return diff.toString(2).split('1').length - 1;
};

复杂度分析

相关题目

• . Minimum Bit Flips to Convert Number (Easy)