收集元素的最少操作次数

You are given an array nums of positive integers and an integer k.

In one operation, you can remove the last element of the array and add it to your collection.

Return the minimum number of operations needed to collect elements 1, 2, ..., k.

 

Example 1:

Input: nums = [3,1,5,4,2], k = 2
Output: 4
Explanation: After 4 operations, we collect elements 2, 4, 5, and 1, in this order. Our collection contains elements 1 and 2. Hence, the answer is 4.

Example 2:

Input: nums = [3,1,5,4,2], k = 5
Output: 5
Explanation: After 5 operations, we collect elements 2, 4, 5, 1, and 3, in this order. Our collection contains elements 1 through 5. Hence, the answer is 5.

Example 3:

Input: nums = [3,2,5,3,1], k = 3
Output: 4
Explanation: After 4 operations, we collect elements 1, 3, 5, and 2, in this order. Our collection contains elements 1 through 3. Hence, the answer is 4.

 

Constraints:

• 1 <= nums.length <= 50
• 1 <= nums[i] <= nums.length
• 1 <= k <= nums.length
• The input is generated such that you can collect elements 1, 2, ..., k.

/*
题目思路：
使用 Java Stream API 我们可以更简洁地实现目标。
我们依然从后往前遍历 nums，每次将元素添加到集合中。
使用 Stream API 的 allMatch 方法来检测集合中是否包含所有目标元素。
*/
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;

public class Solution {
    public int minOperations(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();
        int operations = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            set.add(nums[i]);
            operations++;
            if (IntStream.rangeClosed(1, k).allMatch(set::contains)) {
                return operations;
            }
        }
        return operations;
    }
}

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

O(n)

O(k)