2024-12-11：数组最后一个元素的最小值。用go语言，给定两个整数 n 和 x，构造一个长度为 n 的正整数数组 nums

2024-12-11：数组最后一个元素的最小值。用go语言，给定两个整数 n 和 x，构造一个长度为 n 的正整数数组 nums，使得数组中相邻元素递增且所有元素按位与的结果为 x。返回可能的最小 nums 数组中的最后一个元素的值。

1 <= n, x <= 100000000。

输入：n = 3, x = 4。

输出：6。

解释：

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

答案2024-12-11：

chatgpt[1]

题目来自leetcode3133。

大体步骤如下：

1.计算变量 bitCount，表示 n 和 x 转换为二进制后的位数差。

2.设置初始解 res 为 x，并初始化另一个变量 m 为 n - 1。

3.通过循环处理每个位，检查 res 中每一位是否为 0。

4.如果某位为 0，则检查 m 对应位是否为 1，若是，则将 res 中该位设置为 1。

5.返回最终的 res 值，即可能的最小 nums 数组。

总体时间复杂度：

• 该算法的时间复杂度取决于 bitCount，即 O(bitCount)。

• bitCount 的计算时间复杂度为 O(1)。

• 循环处理每个位的时间复杂度为 O(bitCount)。

• 因此，总的时间复杂度为 O(bitCount)。

总体额外空间复杂度：

• 该算法只使用少量变量来存储数据，额外空间复杂度为 O(1)，即为常量级别的空间消耗。

Go完整代码如下：

package main

import(

"fmt"

"math/bits"

)

func minEnd(n int, x int)int64{

  bitCount :=128- bits.LeadingZeros(uint(n))- bits.LeadingZeros(uint(x))

  res :=int64(x)

  m :=int64(n)-1

  j :=0

for i :=0; i < bitCount; i++{

if res&(1<<i)==0{

if m&(1<<j)!=0{

              res |=1<< i

}

          j++

}

}

return res

}

func main(){

  n :=3

  x :=4

  fmt.Println(minEnd(n, x))

}

在这里插入图片描述Rust完整代码如下：

fn min_end(n:i64, x:i64)->i64{

letbit_count=128- n.leading_zeros()- x.leading_zeros();

letmut res= x asi64;

letm=(n -1)asi64;

letmut j=0;

foriin0..bit_count {

if res &(1<< i)==0{

if m &(1<< j)!=0{

              res |=1<< i;

}

          j +=1;

}

}

  res

}

fnmain(){

letn=3;

letx=4;

println!("{}",min_end(n, x));

}

在这里插入图片描述引用链接