算法练习10——数组为空的最少操作次数

LeetCode 100032 使数组为空的最少操作次数

给你一个下标从 0 开始的正整数数组 nums 。
你可以对数组执行以下两种操作 任意次 ：
从数组中选择 两个 值 相等 的元素，并将它们从数组中 删除 。
从数组中选择 三个 值 相等 的元素，并将它们从数组中 删除 。
请你返回使数组为空的 最少 操作次数，如果无法达成，请返回 -1 。

我的超长代码，没有下面这个sort就超时了…

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        nums.sort()
        times = 0
        repeat_times, repeat_item = 0, nums[0]
        for idx, item in enumerate(nums):
            if item == repeat_item:
                repeat_times += 1
            if item != repeat_item:
                if repeat_times % 3 == 0:
                    times += repeat_times // 3
                elif repeat_times % 3 == 1:
                    if repeat_times > 3:
                        times += repeat_times // 3 - 1 + 2
                    else:
                        return -1
                else:
                    times += repeat_times // 3 + 1
                
                repeat_times = 1
                repeat_item = item
        if repeat_times % 3 == 0:
            times += repeat_times // 3
        elif repeat_times % 3 == 1:
            if repeat_times > 3:
                times += repeat_times // 3 - 1 + 2
            else:
                return -1
        else:
            times += repeat_times // 3 + 1
        
        return times
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

使用Counter和c + 2 // 3完美避免了冗长的代码

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        cnt = Counter(nums)
        if 1 in cnt.values():
            return -1
        return sum((c + 2) // 3 for c in cnt.values())

# 作者：灵茶山艾府
# 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-make-array-empty/
# 来源：力扣（LeetCode）
# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11