Easy

题目描述

给你一个正整数数组 nums 和一个整数 k。

在一次操作中，你可以移除数组的最后一个元素并将其添加到你的集合中。

返回收集元素 1, 2, ..., k 所需的最少操作次数。

示例 1：

输入：nums = [3,1,5,4,2], k = 2
输出：4
解释：经过 4 次操作，我们按顺序收集元素 2, 4, 5, 1。我们的集合包含元素 1 和 2。因此，答案是 4。

示例 2：

输入：nums = [3,1,5,4,2], k = 5
输出：5
解释：经过 5 次操作，我们按顺序收集元素 2, 4, 5, 1, 3。我们的集合包含元素 1 到 5。因此，答案是 5。

示例 3：

输入：nums = [3,2,5,3,1], k = 3
输出：4
解释：经过 4 次操作，我们按顺序收集元素 1, 3, 5, 2。我们的集合包含元素 1 到 3。因此，答案是 4。

提示：

  • 1 <= nums.length <= 50
  • 1 <= nums[i] <= nums.length
  • 1 <= k <= nums.length
  • 输入保证你可以收集到元素 1, 2, ..., k

解题思路

解题思路

由于我们只能从数组末尾移除元素，所以需要从右到左遍历数组，模拟这个过程。

核心思路是使用哈希表或数组来记录我们已经收集到的元素：

  1. 从数组末尾开始遍历，对于每个元素进行一次操作
  2. 如果当前元素在 [1, k] 范围内且还没有被收集过，则标记为已收集
  3. 当我们收集到所有 1 到 k 的元素时，返回当前的操作次数

算法步骤：

  • 使用集合或布尔数组记录已收集的元素
  • 从数组末尾向前遍历，计数操作次数
  • 对于每个有效元素（在范围 [1, k] 内且未收集过），加入已收集集合
  • 当收集到的不同元素数量等于 k 时，返回操作次数

这是一个贪心算法，因为我们必须按照从末尾移除的顺序进行操作，所以只要找到第一个能收集齐所有需要元素的位置即可。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        unordered_set<int> collected;
        int operations = 0;
        
        for (int i = nums.size() - 1; i >= 0; i--) {
            operations++;
            if (nums[i] >= 1 && nums[i] <= k && collected.find(nums[i]) == collected.end()) {
                collected.insert(nums[i]);
                if (collected.size() == k) {
                    return operations;
                }
            }
        }
        
        return operations;
    }
};

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        collected = set()
        operations = 0
        
        for i in range(len(nums) - 1, -1, -1):
            operations += 1
            if 1 <= nums[i] <= k and nums[i] not in collected:
                collected.add(nums[i])
                if len(collected) == k:
                    return operations
        
        return operations

public class Solution {
    public int MinOperations(IList<int> nums, int k) {
        HashSet<int> collected = new HashSet<int>();
        int operations = 0;
        
        for (int i = nums.Count - 1; i >= 0; i--) {
            operations++;
            if (nums[i] >= 1 && nums[i] <= k && !collected.Contains(nums[i])) {
                collected.Add(nums[i]);
                if (collected.Count == k) {
                    return operations;
                }
            }
        }
        
        return operations;
    }
}

var minOperations = function(nums, k) {
    const collected = new Set();
    let operations = 0;
    
    for (let i = nums.length - 1; i >= 0; i--) {
        operations++;
        if (nums[i] >= 1 && nums[i] <= k) {
            collected.add(nums[i]);
        }
        if (collected.size === k) {
            return operations;
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(k)

其中 n 是数组 nums 的长度。最坏情况下需要遍历整个数组，时间复杂度为 O(n)。空间复杂度为 O(k)，用于存储已收集的元素集合。

相关题目