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

孤寂灬无痕字数: 7353 阅读耗时: 18 分钟 2025/06/03 博客独享热度: 22 评论:

给你一个长度为 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] <= 1000
nums[i] 是一个质数。

思路

数学
- ans[i] OR (ans[i] + 1) 必为奇数
- 是质数的偶数只有2，且无结果，即 num[i]=2时，ans[i]=-1
- 设 s = nums[i] + 1，并令 v 为 s 的二进制表示中最低位 1 的位置（即 s 可被2^V整除，但不能被2^{V+1}整除）。则满足条件的最小 ans[i] 为nums[i]-2^{v-1}。
- 推导依据：通过分析 x OR (x + 1) 的二进制性质，可得x | (x + 1) = (y + 1) \cdot 2^k - 1，其中 k 是某个正整数。令其等于质数 p，则p + 1 = (y + 1) \cdot 2^k。因此，p + 1 必须被某个2^K整除。最小 x 对应于最大的 k（即 k = v），此时x=p-2^{v-1}。
- 计算方式：使用位运算高效计算：
  - lsb = s & -s：得到 s 的最低有效位（即2^v）。（一个字：绝）
  - power = lsb >> 1：得到 2^{v-1}（因为 lsb 是 2^v，右移一位得到 2^{v-1}）。
  - ans[i] = nums[i] - power。

代码

数学

class Solution {
    public int[] minBitwiseArray(List<Integer> nums) {
        int[] result = new int[nums.size()];
        int index = 0;
        for (int p : nums) {
            if (p == 2) {
                result[index] = -1;
            } else {
                int s = p + 1;
                int lsb = s & -s;       // 获取最低有效位
                int power = lsb >> 1;   // 计算2^{k-1}
                result[index] = p - power;     // 计算答案
            }
            index++;
        }
        return result;
    }
}