收集元素的最少操作次数

标签: 位运算 数组 哈希表

难度: 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 。

Submission

运行时间: 27 ms

内存: 16.0 MB

from typing import List


class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        vis = [0] * (k + 1)
        cnt = 0
        n = len(nums)
        for i in range(n - 1, -1, -1):
            # 题目中已经保证输入为正整数
            if nums[i] <= k and not vis[nums[i]]:
                # 对于新加入集合的数进行统计
                vis[nums[i]] = 1
                cnt += 1
                if cnt == k:
                    return n - i

Explain

该题解的思路是从数组的末尾开始向前遍历，这是因为题目要求的是收集元素的最少操作次数，而操作仅允许从数组的末尾删除元素。为了统计收集到的元素，使用一个大小为 k+1 的布尔数组 vis 来标记哪些元素已被收集。数组的索引即元素的值。遍历数组的过程中，每遇到一个未收集的目标元素（即小于等于 k 的元素），就标记该元素为已收集，并更新已收集的元素计数器 cnt。一旦 cnt 达到 k，说明已收集到 1 到 k 的所有元素，此时的操作次数即为总长度减去当前索引，因为这表示从数组末尾到当前位置的元素数。

时间复杂度: O(n)

空间复杂度: O(k)

from typing import List


class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        vis = [0] * (k + 1)  # 创建一个标记数组，用来记录数字是否被收集
        cnt = 0  # 记录已经收集到的目标元素的数量
        n = len(nums)  # 数组的总长度
        for i in range(n - 1, -1, -1):  # 从数组末尾开始向前遍历
            if nums[i] <= k and not vis[nums[i]]:  # 检查当前元素是否为目标元素，并且未被收集
                vis[nums[i]] = 1  # 标记为已收集
                cnt += 1  # 增加已收集元素的计数
                if cnt == k:  # 如果已收集到所有目标元素
                    return n - i  # 返回操作次数，即总长度减去当前索引

Explore

从数组末尾开始遍历是为了最小化必须删除的元素数量。题目中提到操作仅允许从数组的末尾删除元素，因此从末尾开始遍历可以直接计算出从当前位置到数组末端的元素数量，这些元素都需要被删除以达到收集目标元素的要求。如果从数组开头或中间开始，将难以直接得到需要删除的元素数，从而无法简单地计算最小操作次数。

在遍历过程中，如果遇到一个已经标记为收集的元素（即在布尔数组 vis 中已被设置为1的元素），我们将忽略这个元素继续遍历，因为它不会再次增加已收集元素的计数器 cnt。这种情况不会对结果产生影响，因为我们只关心是否收集了1到k的所有目标元素，而不是元素出现的次数。

布尔数组 vis 使用 k+1 的大小是为了直接使用元素值作为数组的索引，方便快速检查和标记元素是否已被收集。如果使用 k 的大小，数组的索引将从0到k-1，这意味着我们无法直接用元素值 k 作为索引（因为索引k将超出数组范围）。因此，使用 k+1 的大小可以确保所有目标元素值都有一个对应的索引位置。

一旦确定已收集到所有目标元素，算法将立即停止遍历并返回当前操作的次数，因为此时已经达到了题目要求的最小操作次数的条件。数组中未遍历的部分不会再被考虑，因为它们不影响已达到的结果（即已经收集了1到k的所有目标元素），而继续遍历这部分只会增加不必要的计算，没有实际意义。