class Solution {
public:
int minOperations(vector<int>& nums, int k) {
}
};
8038. 收集元素的最少操作次数
给你一个正整数数组 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 <= 501 <= nums[i] <= nums.length1 <= k <= nums.length1, 2, ..., k 。原站题解
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-10-02 00:07:32
class Solution:
def minOperations(self, nums: List[int], k: int) -> int:
u = (2 << k) - 2 # 1~k
s, n = 0, len(nums)
for i in range(n - 1, -1, -1):
s |= 1 << nums[i]
if (s & u) == u:
return n - i
java 解法, 执行用时: 0 ms, 内存消耗: 39.6 MB, 提交时间: 2023-10-02 00:07:16
class Solution {
public int minOperations(List<Integer> nums, int k) {
int n = nums.size();
long u = (2L << k) - 2; // 1~k
long s = 0;
for (int i = n - 1; ; --i) {
s |= 1L << nums.get(i);
if ((s & u) == u) {
return n - i;
}
}
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 18.8 MB, 提交时间: 2023-10-02 00:06:52
class Solution {
public:
int minOperations(std::vector<int>& nums, int k) {
int n = nums.size();
long long u = (2LL << k) - 2; // 1~k
long long s = 0;
for (int i = n - 1; ; --i) {
s |= 1LL << nums[i];
if ((s & u) == u) {
return n - i;
}
}
}
};
golang 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-02 00:06:40
func minOperations(nums []int, k int) int {
all := 2<<k - 2 // 1~k
set := 0
for i := len(nums) - 1; ; i-- {
set |= 1 << nums[i]
if set&all == all {
return len(nums) - i
}
}
}