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

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

力扣题目链接：https://leetcode.cn/problems/minimum-array-end/
给你两个整数 n 和 x 。你需要构造一个长度为 n 的 正整数 数组 nums ，对于所有 0 <= i < n - 1 ，满足 nums[i + 1] 大于 nums ，并且数组 nums 中所有元素的按位 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 <= 108
  

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

解题思路

所有num与运算的结果为x，说明x二进制下为1的位置在所有num中也全部为1。
那其他位置呢？x二进制下为0的位置呢？当然是可1可0。
由于想要nums数组中最大的那个数尽可能小，所以在填充x非零位置的时间，用从0到                                   n                         −                         1                              n-1                  n−1的二进制填充就好了。如许得到的nums数组即为最优。
总之：将                                        n                            −                            1                                  n-1                     n−1的二进制插入到                                        x                                  x                     x中为0的位置即可。
   假如                                        x                            =                            5                            (                            101                            )                                  x=5(101)                     x=5(101)，那么x中为0的位有：第2位、第4位、第5位、第6位、…。
  假设                                        n                            =                            3                                  n=3                     n=3，那么                                        0                                  0                     0到                                        n                            −                            1                                  n-1                     n−1的2进制为                                        00                                  00                     00、                                        01                                  01                     01、                                        10                                  10                     10。
  将这些数填充到x中为0的位置，即可得到nums数组：0101、0111、1101（加粗的位置是x中为0的位置，填入了0到2这3个数）。
  因此                                        n                            u                            m                            s                                  nums                     nums中最大的数为：将                                        n                            −                            1                                  n-1                     n−1的二进制填入                                        x                                  x                     x二进制下为                                        0                                  0                     0的位置。
  详细做法

由于                                   1                         ≤                         n                         ≤                         1                                   0                            8                                  ≤                                   2                            27                                       1\leq n\leq 10^8 \le 2^{27}                  1≤n≤108≤227，所以只需要考虑                                   n                         −                         1                              n-1                  n−1的低                                   27                              27                  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                            )                                  O(C)                     O(C)，此中                                        C                            =                            log                            ⁡                            (                            max                            ⁡                            {                            n                            ,                            x                            }                            )                            =                            27                                  C=\log(\max\{n, x\})=27                     C=log(max{n,x})=27
  
• 空间复杂度                                        O                            (                            1                            )                                  O(1)                     O(1)
  

AC代码

C++

1. /*
2. 将x每个0的位置设置为n-1的二进制
3. */
4. typedef long long ll;
6. class Solution {
7. public:
8.     ll minEnd(ll n, ll x) {
9.         n--;
10.         for (int in = 0, ix = 0; in < 27; in++, ix++) {
11.             while ((x >> ix) & 1) {  // 找到下一个为0的位置
12.                 ix++;
13.             }
14.             x |= (((n >> in) & 1) << ix);
15.         }
16.         return x;
17.     }
18. };

复制代码

Go

1. package main
3. func minEnd(n int, x int) int64 {
4.     n64, ans := (int64)(n - 1), (int64)(x)
5.     for in, ix := 0, 0; in < 27; in, ix = in + 1, ix + 1 {
6.         for ((ans >> ix) & 1) != 0 {
7.             ix++
8.         }
9.         ans |= (((n64 >> in) & 1) << ix)
10.     }
11.     return ans
12. }

复制代码

Java

1. class Solution {
2.     public long minEnd(long n, long x) {
3.         n--;
4.         for (int in = 0, ix = 0; in < 27; in++, ix++) {
5.             while (((x >> ix) & 1) != 0) {
6.                 ix++;
7.             }
8.             x |= (((n >> in) & 1) << ix);
9.         }
10.         return x;
11.     }
12. }

复制代码

Python

1. class Solution:
2.     def minEnd(self, n: int, x: int) -> int:
3.         n -= 1
4.         ix = 0
5.         for in_ in range(27):
6.             while (x >> ix) & 1:
7.                 ix += 1
8.             x |= (((n >> in_) & 1) << ix)
9.             ix += 1
10.         return x

复制代码

  同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
  Tisfy：https://letmefly.blog.csdn.net/article/details/141440484

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。