2026-01-20-LeetCode刷题笔记-3314-构造最小位运算数组I

---

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。

---

初步思路

1. 观察x | (x + 1)：它会把 x 的“最右侧第一个 0”变成 1，因此结果必然以连续的 1 结尾。
2. 若 y = nums[i]，设 y 末尾连续 1 的个数为 k，则最小的 x 就是把这段连续 1 中最高位的那个 1 清掉。
3. 题面为素数数组，因此只有 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

---

总结与反思

1. 关键在于“最右侧第一个 0 会被置 1”，因此结果以连续 1 结尾。
2. 可以用位运算快速定位要翻转的那一位