2024-10-19：用go语言，给定一个正整数 k 和初始数组 nums = [1]， 可以执行两种操作：将数组中任一元素加一

2024-10-19：用go语言，给定一个正整数 k 和初始数组 nums = [1]，

可以执行两种操作：将数组中任一元素加一，或复制数组中任意元素并将其附加到数组末尾。

求使得数组元素之和大于或等于 k 所需的最少操作次数。

输入：k = 11。

输出：5。

解释：

可以对数组 nums = [1] 执行以下操作：

将元素的值增加 1 三次。结果数组为 nums = [4] 。

复制元素两次。结果数组为 nums = [4,4,4] 。

最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。

执行的总操作次数为 3 + 2 = 5 。

答案2024-10-19：

chatgpt

题目来自leetcode3091。

大体步骤如下：

1.初始数组为 [1].

2.将元素的值增加 1，得到数组 [2]。操作次数 +1.

3.将元素的值增加 1，得到数组 [3]。操作次数 +1.

4.将元素的值增加 1，得到数组 [4]。操作次数 +1.

5.复制元素 4 两次，得到数组 [4, 4, 4]。操作次数 +2.

最终数组中的元素之和为 4 + 4 + 4 = 12，大于等于给定的 k = 11。总的操作次数为 3 + 2 = 5。

时间复杂度：

• • 根据代码实现，时间复杂度为 O(sqrt(k))，主要由计算平方根和取整操作所决定。

空间复杂度：

• • 程序中并没有使用额外空间，因此空间复杂度为 O(1)。

Go完整代码如下：

package main

import(
"fmt"
"math"
)

func minOperations(k int)int{
    rt := max(int(math.Sqrt(float64(k-1))),1)
return min(rt-1+(k-1)/rt, rt+(k-1)/(rt+1))
}

func main(){
    k:=11
    fmt.Println(minOperations(k))
}

Rust完整代码如下：

use std::cmp;

fnmin_operations(k:i32)->i32{
letrt= cmp::max((k asf64-1.0).sqrt()asi32,1);
return cmp::min(rt -1+(k -1)/ rt, rt +(k -1)/(rt +1));
}

fnmain(){
letk=11;
println!("{}",min_operations(k));
}