LeetCode 3133.数组最后一个元素的最小值：位运算+双指针

【LetMeFly】3133.数组最后一个元素的最小值：位运算+双指针

力扣题目链接：https://leetcode.cn/problems/minimum-array-end/

给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums[i] ，并且数组 nums 中所有元素的按位 AND 运算结果为 x 。

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

 

示例 1：

输出：6

解释：

数组 nums 可以是 [4,5,6] ，最后一个元素为 6 。

示例 2：

输出：15

解释：

数组 nums 可以是 [7,15] ，最后一个元素为 15 。

 

提示：

• 1 <= n, x <= 108

解题方法：位运算+双指针

解题思路

所有num与运算的结果为x，说明x二进制下为1的位置在所有num中也全部为1。

那其他位置呢？x二进制下为0的位置呢？当然是可1可0。

因为想要nums数组中最大的那个数尽可能小，所以在填充x非零位置的时候，用从0到$n-1$的二进制填充就好了。这样得到的nums数组即为最优。

总之：将$n-1$的二进制插入到$x$中为0的位置即可。

假如$x=5(101)$，那么x中为0的位有：第2位、第4位、第5位、第6位、…。

假设$n=3$，那么$0$到$n-1$的2进制为$00$、$01$、$10$。

将这些数填充到x中为0的位置，即可得到nums数组：0101、0111、1101（加粗的位置是x中为0的位置，填入了0到2这3个数）。

因此$nums$中最大的数为：将$n-1$的二进制填入$x$二进制下为$0$的位置。

具体做法

由于$1\le n\le 10^8\le 2^{27}$，所以只需要考虑$n-1$的低$27$位即可。

使用两个指针，ix指向x的每一位，in指向n的每一位。

主循环令in从0到26（指向n的每一位），每次ix找到一个x为0的位（当ix指向的那一位为1时，ix增加1移动到下一位），将这一位赋值为in所指的位的值。

• 取出x的第ix位：(x >> ix) & 1
• 取出n的第in位：(n >> in) & 1
• 构造第in位为n的第in位，其余位为0的数：(n >> in) & 1) << ix
• 将x的第ix位赋值为n的第in位：x |= (((n >> in) & 1) << ix)

时空复杂度分析

• 时间复杂度$O(C)$，其中 C = log ⁡ ( max ⁡ { n , x } ) = 27 C=\log(\max\{n, x\})=27 C=log(max{n,x})=27
• 空间复杂度$O(1)$

AC代码

C++

/*
将x每个0的位置设置为n-1的二进制
*/
typedef long long ll;class Solution {
public:ll minEnd(ll n, ll x) {n--;for (int in = 0, ix = 0; in < 27; in++, ix++) {while ((x >> ix) & 1) {  // 找到下一个为0的位置ix++;}x |= (((n >> in) & 1) << ix);}return x;}
};

Go

package mainfunc minEnd(n int, x int) int64 {n64, ans := (int64)(n - 1), (int64)(x)for in, ix := 0, 0; in < 27; in, ix = in + 1, ix + 1 {for ((ans >> ix) & 1) != 0 {ix++}ans |= (((n64 >> in) & 1) << ix)}return ans
}

Java

class Solution {public long minEnd(long n, long x) {n--;for (int in = 0, ix = 0; in < 27; in++, ix++) {while (((x >> ix) & 1) != 0) {ix++;}x |= (((n >> in) & 1) << ix);}return x;}
}

Python

class Solution:def minEnd(self, n: int, x: int) -> int:n -= 1ix = 0for in_ in range(27):while (x >> ix) & 1:ix += 1x |= (((n >> in_) & 1) << ix)ix += 1return x

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

Tisfy：https://letmefly.blog.csdn.net/article/details/141440484