LeetCode 题解工作台
使数组异或和等于 K 的最少操作次数
给你一个下标从 0 开始的整数数组 nums 和一个正整数 k 。 你可以对数组执行以下操作 任意次 ： 选择数组里的 任意 一个元素，并将它的 二进制 表示 翻转 一个数位，翻转数位表示将 0 变成 1 或者将 1 变成 0 。 你的目标是让数组里 所有 元素的按位异或和得到 k ，请你返回达成这…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 数组·结合·位运算·操作
答案摘要
我们可以将数组 中的所有元素进行异或运算，判断得到的结果与 的二进制表示中有多少位不同，这个数就是最少操作次数。 时间复杂度 ，其中 是数组 的长度。空间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·结合·位运算·操作 题型思路
题目描述
给你一个下标从 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 <= 1050 <= nums[i] <= 1060 <= k <= 106
解题思路
方法一：位运算
我们可以将数组 中的所有元素进行异或运算，判断得到的结果与 的二进制表示中有多少位不同，这个数就是最少操作次数。
时间复杂度 ，其中 是数组 的长度。空间复杂度 。
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
return reduce(xor, nums, k).bit_count()
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(N) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Ensure the candidate recognizes the importance of bitwise operations in solving the problem efficiently.
- question_mark
Watch for understanding of XOR properties and how they relate to the problem's requirements.
- question_mark
Look for a clear plan to minimize the number of operations by flipping only necessary bits.
常见陷阱
外企场景- error
Failing to properly calculate the initial XOR of the array, leading to incorrect results.
- error
Misunderstanding the bit manipulation, leading to unnecessary or excessive operations.
- error
Not considering the constraints on the size of the array and the values of the elements, potentially missing optimizations.
进阶变体
外企场景- arrow_right_alt
A variant could involve applying bit flips to certain subarrays, not the entire array.
- arrow_right_alt
Another variant could restrict the number of times each element can be modified.
- arrow_right_alt
A harder variant could involve multiple target XOR values instead of just one k.