[M位运算] lc3133. 数组最后一个元素的最小值(位运算+思维+好题)

本文主要是介绍[M位运算] lc3133. 数组最后一个元素的最小值(位运算+思维+好题)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

链接：3133. 数组最后一个元素的最小值

题单位置:

1. 位运算（基础/性质/拆位/试填/恒等式/思维）
- 二、与或（AND/OR）的性质

2. 题目解析

一道挺有意思的题目。位运算的简单拓展。

主要讲下简单的代码实现方法和思路：

相当于 x 的二进制表示下，0 的位置相当于一个个的空位置，都是待填的空位置。想象一下把这些空位置拿出来放一起，构成一个二进制表示。这个二进制表示下的数，也就唯一对应了这些空位值填 0 、填 1。并且恰好，将二进制数所对应的 10 进制数记为 t，就等价于满足题目要求的第 t 个数，因为我们是从低位到高位有序填写的。那么如果我们要填 n 个数，那就相当于 n 的二进制表示。将它填到 x 的这些空位值上即可。

注意位运算这里，也可能会爆 LL。

踩坑：

一开始想到了只需要关注 x 的 0 位置即可。
然后每个 0 位置的贡献值相当于 2 的倍数。1、2、4、8、16…
然后假设有 x 个 0，那么相当于有 1<< x 种填写情况。
那么只需要枚举到该情况即可。
然后写完 TLE 几次才发现，这不就是 n 的二进制表示填到 x 的空位上吗…淦。

时间复杂度： $O(\log n + \log x)$
空间复杂度： $O (1)$

class Solution {
public:typedef long long LL;long long minEnd(int n, int x) {LL res = x;n -- ;int i = 0, j = 0;   // x 的第 i 位，n 的第 j 位while (n >> j) {if ((res >> i & 1) == 0) {  // j 的每一位填充到 x 的每一个 0 位res |= (LL)(n >> j & 1) << i;j ++ ;}i ++ ;}return res;}
};