Greedy 策略: 最少需要幾次刪除操作讓陣列為空 Leetcode #2870

Tijs van Leur on Unsplash

題目敘述

題目會給我們一個整數陣列，裡面包含各種正整數，每回合可以消去兩個相同的數字，或者消去三個相同的數字。問最少需要幾次消去，才能讓陣列為空? 如果無解，則返回-1

詳細的題目可在這裡看到

測試範例

Input: nums = [2,3,3,2,2,4,2,3,4]
Output: 4
Explanation: We can apply the following operations to make the array empty:
- Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4].
- Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4].
- Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4].
- Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = [].
It can be shown that we cannot make the array empty in less than 4 operations.

Example 2:

Input: nums = [2,1,2,2,3,3]
Output: -1
Explanation: It is impossible to empty the array.

約束條件

Constraints:

• 2 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6

演算法:

首先，題目已經講明每一回合可以消去兩個相同的數字或者三個相同的數字。

接下來，就是確立有解和無解的範圍在哪?

2a + 3b = k 可以表達所有大於等於2的整數，也就是說，任何出現大於等於兩次的數字都是有解的。若題目中存在有只出現一次的數字則無解。

例如:

5,5 可以用一次消去刪掉

5,5,5 可以用一次消去刪掉

5,5,5,5 可以用兩次消去刪掉，第一次消去兩個5，第二次也削去兩個5

5,5,5,5,5 可以用兩次消去刪掉，第一次消去三個5，第二次消去兩個5

5,5,5,5,5,5 可以用兩次消去刪掉，第一次消去三個5，第二次也削去三個5

其他更高次數，依此類推。

最佳解的削去規律是 出現次數 除以 3 ，再檢查是否還有餘數，若有餘數，再額外多加一次。

所以，到這邊可以發現關鍵是每個數字的出現次數。

聯想到用字典(或稱 hash table哈希雜湊表)，先統計每一個數字的出現次數，若題目中存在有只出現一次的數字則無解，直接返回-1。

若是有解，則把出現次數 除以 3 ，再檢查是否還有餘數，若有餘數，再額外多加一次，就可以把數字都削去，變成空陣列。

程式碼

class Solution:
    def minOperations(self, nums: List[int]) -> int:

        ## Dictionary
        # key: distinct number
        # value: occurrence of each number
        num_occ = Counter(nums)

        occurrences = num_occ.values()

        # 1 cannot be eliminated by rule 
        if min( occurrences ) == 1:
            return -1

        # Eliminate each number by greedy strategy with minimal operations
        op = sum( occ // 3 + (occ % 3 > 0) for occ in occurrences)
        return op

複雜度分析

時間複雜度:

O(n)，線性掃描一次，建立一個字典，統計每個數字的出現次數。

空間複雜度:

O(n)，最差情況就是每個數字都不同，只出現一次，這時候字典大小為O(n)

Reference:

[1] Python O(n) by greedy and dictionary [w/ Comment] - Minimum Number of Operations to Make Array Empty - LeetCode