题目信息
- 平台：LeetCode
- 题目：3314. 构造最小位运算数组 I
- 难度：Medium
- 题目链接：Construct the Minimum Bitwise Array I
题目描述
给定一个整数数组 nums（题面为素数数组），对每个 nums[i] 寻找最小的非负整数 x，使得 x | (x + 1) == nums[i]。若不存在这样的 x，返回 -1。
初步思路
- 观察
x | (x + 1)：它会把 x 的“最右侧第一个 0”变成 1，因此结果必然以连续的 1 结尾。 - 若 y = nums[i]，设 y 末尾连续 1 的个数为 k，则最小的 x 就是把这段连续 1 中最高位的那个 1 清掉。
- 题面为素数数组，因此只有 y=2 为偶数且无解，其他 y 都是奇数可处理。
算法分析
- 核心：统计 y 的末尾连续 1 的个数 k，然后
x = y - (1 << (k - 1)) - 技巧：
x | (x + 1)的结果一定是奇数且以连续 1 结尾 - 时间复杂度：O(n * k)，k 为末尾连续 1 的数量（总体很小）
- 空间复杂度：O(1)（不含输出）
代码实现（Python）
解法一：统计末尾连续 1
from typing import List
class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
ans = []
for num in nums:
if num == 2:
ans.append(-1)
continue
k = 0
while num & (1 << k):
k += 1
ans.append(num - (1 << (k - 1)))
return ans解法二：位运算快速定位翻转位
from typing import List
class Solution:
def minBitwiseArray(self, nums: List[int]) -> List[int]:
ans = []
for num in nums:
if num == 2:
ans.append(-1)
continue
t = num ^ (num + 1)
bit = (t + 1) >> 2
ans.append(num ^ bit)
return ans总结与反思
- 关键在于“最右侧第一个 0 会被置 1”，因此结果以连续 1 结尾。
- 可以用位运算快速定位要翻转的那一位
