ToB企服应用市场:ToB评测及商务社交产业平台

标题: LeetCode 3133.数组末了一个元素的最小值：位运算+双指针 [打印本页]
作者: 科技颠覆者    时间: 2024-8-23 17:08
标题: 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 。
 
提示：

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

解题思路

所有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所指的位的值。

时空复杂度分析


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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4