Medium

题目描述

给你一个正整数 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 <= 10^5

解题思路

这道题的核心思路是贪心算法结合枚举。

关键观察：

  1. 最优策略是先执行所有增加操作，再执行所有复制操作
  2. 如果我们将初始元素 1 增加 i 次，得到值为 1 + i
  3. 然后需要复制足够多次，使得总和 ≥ k

具体分析：

  • 假设增加操作次数为 i，那么单个元素值为 1 + i
  • 为了使总和 ≥ k，需要的元素个数至少为 ⌈k / (1 + i)⌉
  • 由于初始有 1 个元素，需要复制的次数为 ⌈k / (1 + i)⌉ - 1
  • 总操作次数为：i + max(0, ⌈k / (1 + i)⌉ - 1)

算法步骤：

  1. 枚举所有可能的增加操作次数 i（从 0 到 k-1）
  2. 对每个 i，计算所需的复制操作次数
  3. 取所有方案中操作次数的最小值

优化： 当 1 + i ≥ k 时，只需要 1 个元素就够了，此时复制操作次数为 0。

代码实现

class Solution {
public:
    int minOperations(int k) {
        if (k == 1) return 0;
        
        int minOps = k - 1; // 最坏情况：只增加不复制
        
        for (int i = 0; i < k; i++) {
            int elementValue = 1 + i;
            int elementsNeeded = (k + elementValue - 1) / elementValue; // 向上取整
            int duplicateOps = elementsNeeded - 1;
            minOps = min(minOps, i + duplicateOps);
        }
        
        return minOps;
    }
};

class Solution:
    def minOperations(self, k: int) -> int:
        if k == 1:
            return 0
        
        min_ops = k - 1  # 最坏情况：只增加不复制
        
        for i in range(k):
            element_value = 1 + i
            elements_needed = (k + element_value - 1) // element_value  # 向上取整
            duplicate_ops = elements_needed - 1
            min_ops = min(min_ops, i + duplicate_ops)
        
        return min_ops

public class Solution {
    public int MinOperations(int k) {
        if (k == 1) return 0;
        
        int minOps = k - 1; // 最坏情况：只增加不复制
        
        for (int i = 0; i < k; i++) {
            int elementValue = 1 + i;
            int elementsNeeded = (k + elementValue - 1) / elementValue; // 向上取整
            int duplicateOps = elementsNeeded - 1;
            minOps = Math.Min(minOps, i + duplicateOps);
        }
        
        return minOps;
    }
}

var minOperations = function(k) {
    if (k === 1) return 0;
    
    let minOps = Infinity;
    
    for (let val = 1; val <= k; val++) {
        let increaseOps = val - 1;
        let duplicateOps = Math.ceil(k / val) - 1;
        minOps = Math.min(minOps, increaseOps + duplicateOps);
    }
    
    return minOps;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(k)需要枚举 0 到 k-1 次增加操作
空间复杂度O(1)只使用常数额外空间