3314.构造最小位运算数组 I：今日先简单题简单做-到II再优化

【LetMeFly】3314.构造最小位运算数组 I：今日先简单题简单做-到II再优化

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

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

解题方法：模拟

今天就每个数$O(1)$的话，明天的每日一题就没得做了。

对于一个数$n$，如何求得其对应的最小$ans$？

使用一个变量从$0$试到$n-1$就好了。

每个数都这样试试，也不用优化，今日的每日一题就这样结束了。

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

AC代码

C++

/*
 * @LastEditTime: 2026-01-20 22:52:17
 */
class Solution {
private:
    int get(int n) {
        for (int i = 0; i <= n; i++) {
            if ((i | (i + 1)) == n) {
                return i;
            }
        }
        return -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]);
        }
        return ans;
    }
};

Python

'''
LastEditTime: 2026-01-20 22:55:49
'''
from typing import List

class Solution:
    def get(self, n: int) -> int:
        for i in range(n):
            if (i | (i + 1)) == n:  # 不是(i or (i + 1))
                return i
        return -1
    
    def minBitwiseArray(self, nums: List[int]) -> List[int]:
        return [self.get(t) for t in nums]

Java

/*
 * @LastEditTime: 2026-01-20 23:04:56
 */
import java.util.List;

class Solution {
    private int get(int n) {
        for (int i = 0; i < n; i++) {
            if ((i | (i + 1)) == n) {
                return i;
            }
        }
        return -1;
    }

    public int[] minBitwiseArray(List<Integer> nums) {
        int[] ans = new int[nums.size()];  // 是size不是length
        for (int i = 0; i < nums.size(); i++) {
            ans[i] = get(nums.get(i));
        }
        return ans;
    }
}

Go

/*
 * @LastEditTime: 2026-01-20 22:58:16
 */
package main

func minBitwiseArray(nums []int) []int {
    get := func(n int) int {
        for i := 0; i < n; i++ {
            if (i | (i + 1)) == n {
                return i
            }
        }
        return -1
    }
    ans := make([]int, len(nums))
    for i, n := range nums {
        ans[i] = get(n)
    }
    return ans
}

Rust

/*
 * @LastEditTime: 2026-01-20 23:07:14
 */
impl Solution {
    fn get(n: i32) -> i32 {
        for i in 0..n {
            if (i | (i + 1)) == n {
                return i;
            }
        }
        -1
    }

    pub fn min_bitwise_array(nums: Vec<i32>) -> Vec<i32> {
        nums.iter().map(|&num| Self::get(num)).collect()
    }
}

Rust - 压缩版(bushi)

/*
 * @LastEditTime: 2026-01-20 23:09:46
 */
impl Solution {
    pub fn min_bitwise_array(nums: Vec<i32>) -> Vec<i32> {
        nums.iter()
            .map(|&n| {
                for i in 0..n {
                    if (i | (i + 1)) == n {
                        return i;
                    }
                }
                -1
            })
            .collect()
    }
}

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

千篇源码题解已开源