要切换二进制数组中的0和1,可以使用 异或操作(XOR)。异或操作具有以下特性,使其适用于此场景:
自反性:
`0 ^ 0 = 0`,`1 ^ 1 = 0`,`0 ^ 1 = 1`,`1 ^ 0 = 1`
即对单个元素进行异或操作会将其自身取反。
局部修改:
异或操作是按位进行的,仅影响参与操作的三个连续元素,不会影响其他位。
具体实现步骤
遍历数组:
从左到右遍历二进制数组 `nums`。
检查条件:
对于每个元素,如果它是 `0`,则执行异或操作:
- 将当前元素与后两个元素(即 `nums[i] ^ nums[i+1] ^ nums[i+2]`)进行异或。
- 由于异或的自反性,`0 ^ 0 ^ 0 = 0`,`0 ^ 0 ^ 1 = 1`,`0 ^ 1 ^ 1 = 0`,`0 ^ 1 ^ 0 = 1`,从而将 `0` 变为 `1`,`1` 变为 `0`。
处理边界情况:
如果当前元素是 `1`,则跳过操作(因为 `1 ^ 0 ^ 1 = 0`,会将其变为 `0`,与目标相反)。
示例代码(Go语言)
```go
func minOperations(nums []int) int {
n := len(nums)
ans := 0
for i := 0; i < n; i++ {
if nums[i] == 0 {
// 检查是否还有至少3个元素
if i+2 >= n {
return -1
}
// 执行异或操作
nums[i] ^= nums[i+1] ^ nums[i+2]
ans++
}
}
return ans
}
```
时间复杂度分析
时间复杂度:O(n),其中 n 是数组的长度。只需遍历一次数组,每次操作固定为3个元素。
空间复杂度:O(1),仅使用常数空间。
注意事项
若无法通过操作将所有元素变为 `1`(例如数组以 `111` 结尾),则返回 `-1`。
该算法假设输入数组长度在 3 到 100,000 之间,满足题目约束。
通过上述方法,可以高效地切换二进制数组中的0和1,满足题目要求。