Medium

题目描述

给你一个由 n 个质数组成的数组 nums。

你需要构造一个长度为 n 的数组 ans，使得对于每个索引 i，ans[i] 和 ans[i] + 1 的按位或等于 nums[i]，即 ans[i] OR (ans[i] + 1) == nums[i]。

此外，你必须最小化结果数组中每个 ans[i] 的值。

如果无法找到满足条件的 ans[i] 值，则设置 ans[i] = -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] <= 10^9
  • nums[i] 是质数

提示：

  • 考虑 nums[i] 的二进制表示。
  • 对于偶数 nums[i]，答案是 -1。
  • 尝试取消 nums[i] 的单个位。

解题思路

这是一个位操作问题，核心是理解 x OR (x+1) 的性质。

首先分析什么情况下无解：如果 nums[i] 是偶数，那么其二进制末位为0。但任何数 x 与 x+1 的按位或结果的末位必为1（因为 x 和 x+1 中必有一个末位为1），因此偶数无解，返回-1。

对于奇数 nums[i]，我们需要找到最小的 x 使得 x OR (x+1) = nums[i]。

关键观察：当 x 的某一位为0而 x+1 的对应位为1时，按位或结果该位为1。考虑加法进位的特点：

  • 如果 x 的二进制末尾有 k 个连续的1，那么 x+1 会使这些1变为0，并在第 k+1 位产生进位
  • 例如：x = ...0111，那么 x+1 = ...1000

因此，x OR (x+1) 会在原来 x 为0的最低位以及所有更低的位都置为1。

算法思路：

  1. 如果 nums[i] 是偶数，返回-1
  2. 找到 nums[i] 二进制中最低的0位（从右数第二个位开始找）
  3. 将该位置0，得到的结果就是最小的 x

具体实现：从 nums[i] 的第1位（次低位）开始，找到第一个为0的位，将其置0即可。

代码实现

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> ans;
        for (int num : nums) {
            if (num % 2 == 0) {
                ans.push_back(-1);
            } else {
                int result = num;
                for (int i = 1; i < 32; i++) {
                    if ((num & (1 << i)) == 0) {
                        result = num ^ (1 << (i - 1));
                        break;
                    }
                }
                ans.push_back(result);
            }
        }
        return ans;
    }
};

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        ans = []
        for num in nums:
            if num % 2 == 0:
                ans.append(-1)
            else:
                result = num
                for i in range(1, 32):
                    if (num & (1 << i)) == 0:
                        result = num ^ (1 << (i - 1))
                        break
                ans.append(result)
        return ans

public class Solution {
    public int[] MinBitwiseArray(IList<int> nums) {
        int[] ans = new int[nums.Count];
        for (int i = 0; i < nums.Count; i++) {
            if (nums[i] % 2 == 0) {
                ans[i] = -1;
            } else {
                int result = nums[i];
                for (int j = 1; j < 32; j++) {
                    if ((nums[i] & (1 << j)) == 0) {
                        result = nums[i] ^ (1 << (j - 1));
                        break;
                    }
                }
                ans[i] = result;
            }
        }
        return ans;
    }
}

var minBitwiseArray = function(nums) {
    const result = [];
    
    for (let num of nums) {
        if (num === 2) {
            result.push(-1);
            continue;
        }
        
        // Find the rightmost 0 bit in num
        let pos = 0;
        let temp = num;
        while ((temp & 1) === 1) {
            temp >>= 1;
            pos++;
        }
        
        // Clear the bit at position pos-1
        const ans = num & ~(1 << (pos - 1));
        result.push(ans);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × log(max(nums)))
空间复杂度O(1)

其中 n 是数组长度，log(max(nums)) 是数字的位数（最多32位）。