title: 2026-01-20-LeetCode刷题笔记-3314-构造最小位运算数组I
date: 2026-01-20
tags:
- 算法学习
- LeetCode
- 位运算
题目信息
- 平台：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
fromtypingimportListclassSolution:defminBitwiseArray(self,nums:List[int])->List[int]:ans=[]fornuminnums:ifnum==2:ans.append(-1)continuek=0whilenum&(1<<k):k+=1ans.append(num-(1<<(k-1)))returnans解法二：位运算快速定位翻转位
fromtypingimportListclassSolution:defminBitwiseArray(self,nums:List[int])->List[int]:ans=[]fornuminnums:ifnum==2:ans.append(-1)continuet=num^(num+1)bit=(t+1)>>2ans.append(num^bit)returnans总结与反思
- 关键在于“最右侧第一个 0 会被置 1”，因此结果以连续 1 结尾。
- 可以用位运算快速定位要翻转的那一位
