Easy

题目描述

给你一个由 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] <= 1000
  • nums[i] 是质数

提示：

  • 约束很小，允许直接遍历所有可能的 ans[i] 值。

解题思路

解题思路

这是一道位运算题目。我们需要找到最小的 x，使得 x | (x + 1) == target。

暴力搜索解法： 由于约束条件很小（nums[i] <= 1000），我们可以直接暴力搜索。对于每个目标值，从 0 开始遍历，找到第一个满足条件的值即为答案。

位运算优化解法： 观察 x | (x + 1) 的特点：

  • 当 x 和 x + 1 进行按位或运算时，结果会在某些位上置 1
  • 如果目标值的最低位是 0，那么无解（因为任何 x | (x + 1) 的最低位都是 1）
  • 我们可以通过分析位模式来直接计算答案

核心观察：

  • 如果 target 是偶数，无解
  • 如果 target 是奇数，我们需要找到合适的 x，使得 x 的某一位从 0 变为 1 后（通过加 1 操作）能够得到目标值

由于约束较小，暴力搜索是最直接且容易理解的方法。

代码实现

class Solution {
public:
    vector<int> minBitwiseArray(vector<int>& nums) {
        vector<int> result;
        
        for (int num : nums) {
            int ans = -1;
            
            // 暴力搜索从 0 到 num-1
            for (int x = 0; x < num; x++) {
                if ((x | (x + 1)) == num) {
                    ans = x;
                    break;
                }
            }
            
            result.push_back(ans);
        }
        
        return result;
    }
};

class Solution:
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        result = []
        
        for num in nums:
            ans = -1
            
            # 暴力搜索从 0 到 num-1
            for x in range(num):
                if (x | (x + 1)) == num:
                    ans = x
                    break
            
            result.append(ans)
        
        return result

public class Solution {
    public int[] MinBitwiseArray(IList<int> nums) {
        int[] result = new int[nums.Count];
        
        for (int i = 0; i < nums.Count; i++) {
            int num = nums[i];
            int ans = -1;
            
            // 暴力搜索从 0 到 num-1
            for (int x = 0; x < num; x++) {
                if ((x | (x + 1)) == num) {
                    ans = x;
                    break;
                }
            }
            
            result[i] = ans;
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
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 in num
        result.push(num & ~(1 << pos));
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × m)，其中 n 是数组长度，m 是数组中的最大值
空间复杂度O(1)，不考虑输出数组的空间