class Solution {
public:
int minOperations(int k) {
}
};
100228. 执行操作使数据元素之和大于等于 K
给你一个正整数 k 。最初，你有一个数组 nums = [1] 。
你可以对数组执行以下 任意 操作 任意 次数（可能为零）：
1 。返回使得最终数组元素之 和 大于或等于 k 所需的 最少 操作次数。
示例 1：
输入：k = 11
输出：5
解释：
可以对数组 nums = [1] 执行以下操作：
1 三次。结果数组为 nums = [4] 。nums = [4,4,4] 。最终数组的和为 4 + 4 + 4 = 12 ，大于等于 k = 11 。
执行的总操作次数为 3 + 2 = 5 。
示例 2：
输入：k = 1
输出：0
解释：
原始数组的和已经大于等于 1 ，因此不需要执行操作。
提示：
1 <= k <= 105原站题解
golang 解法, 执行用时: 3 ms, 内存消耗: 2.1 MB, 提交时间: 2024-03-24 23:01:05
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 minOperations2(k int) int {
ans := math.MaxInt
for m := 1; m <= k; m++ {
ans = min(ans, m-1+(k-1)/m)
}
return ans
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 7.2 MB, 提交时间: 2024-03-24 23:00:39
class Solution {
public:
int minOperations(int k) {
int ans = INT_MAX;
for (int m = 1; m <= k; m++) {
ans = min(ans, m - 1 + (k - 1) / m);
}
return ans;
}
int minOperations2(int k) {
int rt = max((int) sqrt(k - 1), 1);
return min(rt - 1 + (k - 1) / rt, rt + (k - 1) / (rt + 1));
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 39.6 MB, 提交时间: 2024-03-24 23:00:11
class Solution {
public int minOperations(int k) {
int rt = Math.max((int) Math.sqrt(k - 1), 1);
return Math.min(rt - 1 + (k - 1) / rt, rt + (k - 1) / (rt + 1));
}
public int minOperations2(int k) {
int ans = Integer.MAX_VALUE;
for (int m = 1; m <= k; m++) {
ans = Math.min(ans, m - 1 + (k - 1) / m);
}
return ans;
}
}
python3 解法, 执行用时: 118 ms, 内存消耗: 16.3 MB, 提交时间: 2024-03-24 22:59:40
class Solution:
def minOperations(self, k: int) -> int:
return min(m - 1 + (k - 1) // m for m in range(1, k + 1))
def minOperations2(self, k: int) -> int:
rt = max(isqrt(k - 1), 1)
return min(rt - 1 + (k - 1) // rt, rt + (k - 1) // (rt + 1))