【LeetCode 每日一题】3314. 构造最小位运算数组 I —— （解法二） - 详解

Problem:3314. 构造最小位运算数组 I

文章目录

• 1. 整体思路与数学推导
• • • 核心观察
    • 逆向求解
• 2. 完整代码
• 3. 时空复杂度
• • • 时间复杂度：$O(N)$
    • 空间复杂度：$O(N)$

1. 整体思路与数学推导

核心观察

方程 $x\mid (x+1)=\text{num}$的位运算行为如下：

• 加法进位：$x+1$ 会找到 $x$二进制表示中从最低位开始连续的所有的 1，把它们变成 0，并将紧邻的高位 0 变成 1。
  • 设 $x=\dots 0\underset{k\text{个}}{\underbrace{11\dots 1}}$.
  • 则 $x+1=\dots 1\underset{k\text{个}}{\underbrace{00\dots 0}}$.
• 或运算：$x\mid (x+1)$会合并这两个结果。
  • $x\mid (x+1)=\dots 1\underset{k\text{个}}{\underbrace{11\dots 1}}$.
  • 结论：运算结果 num 的二进制形式一定是：某一位 0 被变成了 1，且其右侧（低位）原本全是 1。

逆向求解

给定 num，我们要还原最小的 x：

1. 奇偶性检查：

   • 如果 num 是偶数，二进制末尾是 0。由于 $x\mid (x+1)$ 必然把最低位的 0 填满成 1 甚至是更高的进位，结果一定是奇数。

2. 寻找模式：

   • num 的二进制形式必然是 ...011...1。
   • 我们要找的 x 就是把这串连续 1 中最左边（最高位）的那个 1 变回 0。
   • 例如：num = 10111 (23)。
     • 末尾连续的 1 是 111。
     • 我们要找的 x 是 10011 (19)。
     • 验证：$19|20=10011|10100=10111=23$。对！

3. 位运算技巧：

   • 取反~x：把末尾的连续 1 变成连续 0，紧邻的高位 0 变成 1。
     • x = ...0111, ~x = ...1000.
   • Lowbitt & -t：提取二进制中最右侧的 1。
     • 对于 ~x，最右侧的 1 恰好对应原数 x 中第一个非 1 的位置（即连续 1 左边的那个 0）。
     • 但这还不是我们想要的。我们需要定位的是连续 1 中最高位的那个 1。
   • 实际逻辑调整：
     • 代码中的 lowbit 实际上找的是 x 中最低位的 0所对应的权值。
     • 例如 x = 10111 (23)。~x 末尾是 ...01000。lowbit 是 8 (1000)。
     • 这个 8 对应的是 x 中的那个 0。
     • 我们要消除的 1 是这个 0右边一位的 1。
     • 所以：lowbit >> 1 就是我们要消除的那个 1 的掩码。
     • x ^ (lowbit >> 1)：通过异或操作，将该位翻转（从 1 变 0）。

2. 完整代码

import java.util.List;
class Solution {
public int[] minBitwiseArray(List<Integer> nums) {int n = nums.size();int[] ans = new int[n];for (int i = 0; i < n; i++) {int x = nums.get(i);// 特判：如果 x 是 2 (二进制 10)，无法由 x|(x+1) 生成// 因为偶数（除了可能的位溢出情况）通常无法作为结果// 题目可能设定 x=2 时无解if (x == 2) {ans[i] = -1;} else {// 1. 取反：~x// 假设 x = ...0111 (二进制)// 则 ~x = ...1000int t = ~x;// 2. 求 lowbit：t & -t// 提取出 ~x 中最低位的 1。// 这个 1 对应的是原数 x 中从低位向高位看的"第一个 0"的位置。// 比如 x=...0111，这个 0 就是 111 左边的那个位。int lowbit = t & -t;// 3. 计算结果：x ^ (lowbit >> 1)// lowbit >> 1 得到的是 x 中"连续 1 序列"的最高位。// 用异或 (^) 将该位从 1 变成 0，即得到了满足条件的最小 x。// 例如 x = 10111 (23), 0 在第 4 位(值8), lowbit=8。// lowbit >> 1 = 4 (100)。// 23 ^ 4 = 10111 ^ 00100 = 10011 (19)。ans[i] = x ^ (lowbit >> 1);}}return ans;}}

3. 时空复杂度

假设 nums 的长度为 $N$。

时间复杂度：$O(N)$

• 计算依据：
  • 代码只遍历了一次输入数组。
  • 循环内部全是位运算（取反、与、移位、异或），这些都是 CPU 的根本指令，耗时$O(1)$。
  • 没有嵌套循环，没有递归。
• 结论：$O(N)$。这是处理此类问题的理论最优复杂度。

空间复杂度：$O(N)$

• 计算依据：
  • 使用了一个长度为$N$ 的数组 ans 来存储结果。
• 结论：$O(N)$。