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

标签: 位运算 数组

难度: Medium

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

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

  • 选择数组里的 任意 一个元素，并将它的 二进制 表示 翻转 一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。

你的目标是让数组里 所有 元素的按位异或和得到 k ，请你返回达成这一目标的 最少 操作次数。

注意，你也可以将一个数的前导 0 翻转。比方说，数字 (101)2 翻转第四个数位，得到 (1101)2 。

示例 1：

输入：nums = [2,1,3,4], k = 1
输出：2
解释：我们可以执行以下操作：
- 选择下标为 2 的元素，也就是 3 == (011)2 ，我们翻转第一个数位得到 (010)2 == 2 。数组变为 [2,1,2,4] 。
- 选择下标为 0 的元素，也就是 2 == (010)2 ，我们翻转第三个数位得到 (110)2 == 6 。数组变为 [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 <= 105
  • 0 <= nums[i] <= 106
  • 0 <= k <= 106

Submission

运行时间: 62 ms

内存: 27.1 MB

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        return (reduce(xor, nums) ^ k).bit_count()

Explain

此题解的核心思路是首先计算数组 nums 中所有元素的按位异或和（我们称之为 tmp）。接着，为了得到目标的异或和 k，需要计算 tmp 与 k 的异或结果（tmp ^ k）。这个结果表示 tmp 和 k 在二进制表示中不同的位。因此，要将数组的异或和变为 k，需要改变这些不同位的数量。通过使用 Python 中的 bit_count() 方法，可以快速计算出 tmp ^ k 中值为 1 的位的数量，这些就是需要翻转的位数，也就是最少操作次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        tmp = 0  # 初始化异或结果为0
        for x in nums:  # 遍历数组
            tmp ^= x  # 计算所有元素的异或和
        return (tmp ^ k).bit_count()  # 计算 tmp 与 k 的异或结果中1的个数，即最少操作次数

Explore

异或运算有个特性：相同的数异或结果为0，不同的数异或结果为1。当我们计算数组元素的异或和与目标值k的异或结果时，结果中的每个1代表了当前位上数组异或和与k的数值不同，需要通过翻转来修改。因此，这个异或结果直接指示了哪些位数是不同的，从而需要改变以使得数组的异或和等于k。

是的，异或操作符合交换律和结合律。这意味着无论元素的顺序如何，或者怎样分组进行异或运算，其结果都是一样的。因此，使用 reduce 函数结合异或操作来累计数组中所有元素的异或和是有效且正确的。

在Python中，整数类型是动态大小的，并在内部以补码形式表示。当我们计算异或结果时，前导零通常不影响结果的有效位。bit_count() 函数计算的是结果中1的个数，不考虑前导零，因此可以准确统计出需要翻转的位数，无论数字的实际位数如何。

数字的大小不会直接影响算法的时间复杂度，因为无论数字多大，异或操作的时间复杂度依然是常数时间（取决于数字的位数，但对于任何具体的计算机，这通常是固定的）。然而，更大的数字可能会导致更多的位被设置为1，这可能会增加需要翻转的位数，从而增加达到目标k所需的最小操作次数。