Medium

题目描述

给你两个整数 n 和 x。你需要构造一个正整数数组 nums，长度为 n，其中对于每个 0 <= i < n - 1，都有 nums[i + 1] > nums[i]，并且数组中所有元素按位与（AND）的结果等于 x。

返回 nums[n - 1] 的最小可能值。

示例 1：

输入：n = 3, x = 4
输出：6
解释：nums 可以是 [4,5,6]，其最后一个元素是 6。

示例 2：

输入：n = 2, x = 7
输出：15
解释：nums 可以是 [7,15]，其最后一个元素是 15。

约束条件：

  • 1 <= n, x <= 10^8

提示：

  • 数组的每个元素都应该通过"合并" x 和 v 得到，其中 v = 0, 1, 2, ...(n-1)。
  • 要将 x 与另一个数字 v 合并，保持 x 的置位位不变，对于所有其他位，从右到左按顺序逐一填充 v 的置位位。
  • 因此最终答案是 x 和 n-1 的"合并"。

解题思路

这道题的核心思想是位操作和贪心算法。

问题分析：

  • 要构造长度为 n 的递增数组，使得所有元素的按位与结果等于 x
  • 由于按位与的性质，如果某一位在 x 中是1，那么数组中所有元素在该位置都必须是1
  • 如果某一位在 x 中是0，那么该位置可以灵活设置为0或1来构造不同的数值

解题思路：

  1. 首先理解"合并"操作：保持 x 中为1的位不变，在 x 中为0的位置填入另一个数的位
  2. 要得到最小的第 n 个元素，我们需要将 x 与 (n-1) 进行合并
  3. 具体做法：遍历 x 中为0的位置，从右到左依次填入 (n-1) 的二进制位

算法步骤：

  • 从 x 开始，找到所有为0的位置
  • 将 (n-1) 的二进制表示从低位到高位依次填入这些0位置
  • 最终得到的数就是答案

这种方法确保了构造出的数组是严格递增的，且所有元素的按位与结果等于 x。

代码实现

class Solution {
public:
    long long minEnd(int n, int x) {
        long long result = x;
        long long remaining = n - 1;
        long long position = 1;
        
        while (remaining > 0) {
            if ((x & position) == 0) {
                result |= (remaining & 1) * position;
                remaining >>= 1;
            }
            position <<= 1;
        }
        
        return result;
    }
};

class Solution:
    def minEnd(self, n: int, x: int) -> int:
        result = x
        remaining = n - 1
        position = 1
        
        while remaining > 0:
            if (x & position) == 0:
                result |= (remaining & 1) * position
                remaining >>= 1
            position <<= 1
        
        return result

public class Solution {
    public long MinEnd(int n, int x) {
        long result = x;
        long remaining = n - 1;
        long position = 1;
        
        while (remaining > 0) {
            if ((x & position) == 0) {
                result |= (remaining & 1) * position;
                remaining >>= 1;
            }
            position <<= 1;
        }
        
        return result;
    }
}

var minEnd = function(n, x) {
    let result = x;
    let remaining = n - 1;
    let pos = 0;
    
    while (remaining > 0) {
        if ((x & (1 << pos)) === 0) {
            if (remaining & 1) {
                result |= (1 << pos);
            }
            remaining >>= 1;
        }
        pos++;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)需要遍历 n-1 的二进制位数
空间复杂度O(1)只使用常数额外空间