3315.构造最小位运算数组 II：位运算

【LetMeFly】3315.构造最小位运算数组 II：位运算

力扣题目链接：https://leetcode.cn/problems/construct-the-minimum-bitwise-array-ii/

给你一个长度为 n 的质数数组 nums 。你的任务是返回一个长度为 n 的数组 ans ，对于每个下标 i ，以下 条件 均成立：

• ans[i] OR (ans[i] + 1) == nums[i]

除此以外，你需要 最小化 结果数组里每一个 ans[i] 。

如果没法找到符合 条件 的 ans[i] ，那么 ans[i] = -1 。

质数 指的是一个大于 1 的自然数，且它只有 1 和自己两个因数。

 

示例 1：

输入：nums = [2,3,5,7]

输出：[-1,1,4,3]

解释：

• 对于 i = 0 ，不存在 ans[0] 满足 ans[0] OR (ans[0] + 1) = 2 ，所以 ans[0] = -1 。
• 对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 3 的最小 ans[1] 为 1 ，因为 1 OR (1 + 1) = 3 。
• 对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 5 的最小 ans[2] 为 4 ，因为 4 OR (4 + 1) = 5 。
• 对于 i = 3 ，满足 ans[3] OR (ans[3] + 1) = 7 的最小 ans[3] 为 3 ，因为 3 OR (3 + 1) = 7 。

示例 2：

输入：nums = [11,13,31]

输出：[9,12,15]

解释：

• 对于 i = 0 ，满足 ans[0] OR (ans[0] + 1) = 11 的最小 ans[0] 为 9 ，因为 9 OR (9 + 1) = 11 。
• 对于 i = 1 ，满足 ans[1] OR (ans[1] + 1) = 13 的最小 ans[1] 为 12 ，因为 12 OR (12 + 1) = 13 。
• 对于 i = 2 ，满足 ans[2] OR (ans[2] + 1) = 31 的最小 ans[2] 为 15 ，因为 15 OR (15 + 1) = 31 。

 

提示：

• 1 <= nums.length <= 100
• 2 <= nums[i] <= 109
• nums[i] 是一个质数。

解题方法：位运算

解题思路

假设一个数的二进制是10111，那么最小的$ans$是多少？

想让$ans$尽可能小，就要$ans$高位尽可能小。

$ans$对应的10111最高位的1有可能是0吗（$ans$为0xxxx）？

不可能。

如果$ans$为0xxxx，那么$ans+1$就要为1xxxx，那么$ans$就要为01xxx，那么$ans\ \text{or}\ (ans+1)$一定是11xxx不可能是10xxx。

所以$ans$一定为1xxxx。

$ans$对应的10111第二高位的1有可能是0吗（$ans$为100xx）？

有可能。

$ans$为10011就好。此时$ans+1$为10100，它们或的结果正好是10111。

不难发现，最终结果二进制低位是连续的111，此时$ans$可以为011，$ans+1$为100，或起来正好是111。

$ans$不能再小了，否则两个$0$，怎么或也或不回都是$1$了。

此外，如果$n$是偶数，则不存在$ans$（因为$ans$或$ans+1$一定为奇数），返回$-1$。

具体做法

讨论奇数情况：

使用一个变量$now=1$不断与$n$与，结果非零就令$n$左移一位，最终结果为$0$就得到了$n$最高位连续$1$的高一位。

$n$异或（或者减去）右移一位的$now$即为答案。

时空复杂度分析

• 时间复杂度$O(len(nums)\times\log nums[i])$
• 空间复杂度$O(1)$，力扣返回值不计入算法空间复杂度

AC代码

C++

/*
 * @LastEditTime: 2026-01-21 23:39:44
 */
/*
111
11 | 100

10111 (1+2+4+16=23)
10011 | 10100   (10011:1+2+16=19)

101
100 | 101

110
101 | 110 X

10
1 | 10 X
*/
class Solution {
private:
    int get(int n) {
        if (!(n & 1)) {
            return -1;
        }
        int now = 1;
        while (n & now) {
            now <<= 1;
            // printf("now = %d\n", now);
        }
        return n ^ (now >> 1);
    }
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> ans(nums.size());
        for (int i = 0; i < nums.size(); i++) {
            ans[i] = get(nums[i]);  // 是nums[i]!!! 刚开始又写成i了
        }
        return ans;
    }
};

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源