算法练习9——收集元素的最少操作次数

LeetCode 8038 收集元素的最少操作次数

给你一个正整数数组 nums 和一个整数 k 。
一次操作中，你可以将数组的最后一个元素删除，将该元素添加到一个集合中。
请你返回收集元素 1, 2, …, k 需要的最少操作次数。

class Solution:def minOperations(self, nums: List[int], k: int) -> int:array = [0] * ktimes = 0for i in range(len(nums) - 1, -1, -1):times += 1if nums[i] <= k and array[nums[i] - 1] == 0:array[nums[i] - 1] = timesreturn max(array)

还可以提前跳出循环

class Solution:def minOperations(self, nums: List[int], k: int) -> int:array = [0] * ktimes = 0p = 0for i in range(len(nums) - 1, -1, -1):times += 1if nums[i] <= k and array[nums[i] - 1] == 0:array[nums[i] - 1] = timesp += 1if p == k:breakreturn max(array)

上面的计数数组就是一个哈希表map，本题正好可以使用bit压缩数组
由于元素范围在 [1,50][1,50][1,50]，我们可以用一个 646464 位整数表示集合

class Solution:def minOperations(self, nums: List[int], k: int) -> int:u = (2 << k) - 2  # 1~ks, n = 0, len(nums)for i in range(n - 1, -1, -1):s |= 1 << nums[i]if (s & u) == u:return n - i# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/minimum-operations-to-collect-elements/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。