LeetCode 题解工作台
执行操作使数据元素之和大于等于 K
给你一个 正整数 k 。最初，你有一个数组 nums = [1] 。 你可以对数组执行以下 任意 操作 任意 次数（ 可能为零 ）： 选择数组中的任何一个元素，然后将它的值 增加 1 。 复制数组中的任何一个元素，然后将它附加到数组的末尾。 返回使得最终数组元素之 和 大于或等于 k 所需的 最少 …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们应该将复制的操作（即操作 ）放后面，这样可以减少操作次数。 因此，我们在 $[0, k]$ 的范围内枚举操作 的次数 ，那么操作 的次数 $b = \left\lceil \frac{k}{a+1} \right\rceil - 1$。取最小的 即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你一个正整数 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
解题思路
方法一：枚举
我们应该将复制的操作（即操作 ）放后面，这样可以减少操作次数。
因此，我们在 的范围内枚举操作 的次数 ，那么操作 的次数 。取最小的 即可。
时间复杂度 ，其中 为输入的正整数 。空间复杂度 。
class Solution:
def minOperations(self, k: int) -> int:
ans = k
for a in range(k):
x = a + 1
b = (k + x - 1) // x - 1
ans = min(ans, a + b)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of greedy strategies in optimizing sum with minimal operations.
- question_mark
Check the candidate’s ability to prioritize operations effectively.
- question_mark
Evaluate how well the candidate validates their approach using mathematical principles and invariant rules.
常见陷阱
外企场景- error
Misprioritizing operations, leading to excess operations before reaching k.
- error
Failing to account for the efficient handling of duplicate operations.
- error
Neglecting invariant validation that ensures all operations move toward the target sum.
进阶变体
外企场景- arrow_right_alt
What if nums starts with more elements than just [1]?
- arrow_right_alt
What if the array is very large, requiring different optimization strategies?
- arrow_right_alt
How can this problem be approached with dynamic programming for different constraints?