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

更新於 發佈於 閱讀時間約 5 分鐘

題目敘述

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

詳細的題目可在這裡看到


測試範例

Example 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

avatar-img
91會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key Table:
題目敘述 題目會給我們兩張資料表。 第一張資料表是Employees 裡面分別有id、name等欄位。這張資料表的id是主鍵。 第二張資料表是EmployeeUNI 裡面分別有id、unique_id等欄位。 題目要求我們列出每位員工對應到的Unique ID
題目敘述 題目會給我們一張Tweets資料表。裡面分別有tweet_id、content等欄位。這張資料表的tweet_id是主鍵Primary key。 題目要求我們列出所有非法的推文。輸出順序不拘。 非法推文的定義,推文內容的長度超過15個字元。
題目敘述 題目會給我們一個鏈結串列的起點head,要求我們找出這個串列的中點。 註: 如果串列長度是偶數,就回傳中間偏右的那個節點。 例如: 1 -> 2 -> 3 回傳中點為2 1 -> 2 -> 3 -> 4 ->5 -> 6 回傳中點為4 詳細的題目可在這裡看到 測試範例
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
題目敘述 題目會給我們一個輸入陣列prices分別代表不同交易日的股票價格,問我們在帶有冷卻條件的情況下,不限制交易次數,請問作多的最大獲利是多少? 冷卻條件的定義: 賣出股票的下一天,不能買入股票。 也就是說第i天賣出股票,最快要在i+2天才可以選擇買入股票。
題目敘述 題目會給我們兩張資料表,第一張是Sales,第二張是Product。 第一張是Sales表格,裡面分別有sale_id、 product_id、year、quantity、price等欄位。其中(sale_id、 product_id)做為複合主鍵Primary key Table:
題目敘述 題目會給我們兩張資料表。 第一張資料表是Employees 裡面分別有id、name等欄位。這張資料表的id是主鍵。 第二張資料表是EmployeeUNI 裡面分別有id、unique_id等欄位。 題目要求我們列出每位員工對應到的Unique ID
題目敘述 題目會給我們一張Tweets資料表。裡面分別有tweet_id、content等欄位。這張資料表的tweet_id是主鍵Primary key。 題目要求我們列出所有非法的推文。輸出順序不拘。 非法推文的定義,推文內容的長度超過15個字元。
題目敘述 題目會給我們一個鏈結串列的起點head,要求我們找出這個串列的中點。 註: 如果串列長度是偶數,就回傳中間偏右的那個節點。 例如: 1 -> 2 -> 3 回傳中點為2 1 -> 2 -> 3 -> 4 ->5 -> 6 回傳中點為4 詳細的題目可在這裡看到 測試範例
題目敘述 題目會告訴我們一組英文和數字之間的轉換編碼規則,還有一個輸入字串s,問我總共有多少合法的解碼方式? 要特別留意,輸入字串可能包含有leading zero,導致無法解碼。 轉換規則如下: A <-> 1 B <-> 2 C <-> 3 ... Z <-> 26 詳細的題
題目敘述 題目會給我們一個輸入陣列prices分別代表不同交易日的股票價格,問我們在帶有冷卻條件的情況下,不限制交易次數,請問作多的最大獲利是多少? 冷卻條件的定義: 賣出股票的下一天,不能買入股票。 也就是說第i天賣出股票,最快要在i+2天才可以選擇買入股票。
你可能也想看
Google News 追蹤
Thumbnail
大家好,我是woody,是一名料理創作者,非常努力地在嘗試將複雜的料理簡單化,讓大家也可以體驗到料理的樂趣而我也非常享受料理的過程,今天想跟大家聊聊,除了料理本身,料理創作背後的成本。
Thumbnail
哈囉~很久沒跟各位自我介紹一下了~ 大家好~我是爺恩 我是一名圖文插畫家,有追蹤我一段時間的應該有發現爺恩這個品牌經營了好像.....快五年了(汗)時間過得真快!隨著時間過去,創作這件事好像變得更忙碌了,也很開心跟很多厲害的創作者以及廠商互相合作幫忙,還有最重要的是大家的支持與陪伴🥹。  
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
題目敘述 624. Maximum Distance in Arrays 給定一個輸入二維陣列arrays。 請計算的陣列距離是多少? 陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
Thumbnail
題目敘述: 給定一個傳統手機鍵盤,如圖所示 接著給定一個字串word。 現在讓你重新安排每個字母的所在位置,每個字母可以重新安排到2~9這幾個鍵盤上的位置,每個字母限定只能選擇一個數字鍵去對應。 請問重新安排之後,最少要幾次按鍵才能輸出字串word?
Thumbnail
題目敘述 Most Profit Assigning Work 公司裡有n位員工,m件任務。 每位員工的能力記錄在worker陣列。 每個任務對應的能力要求和獲利紀錄在difficulty 和profit陣列。 不同的員工可以做同樣的任務。 請問怎麼分配任務可以得到整體最大獲利?
Thumbnail
題目敘述 Patching Array 題目給定一個整數陣列, 請問還要補上多少個數字,才能用這些數字的和拼湊出所有1~n的整數。
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,
Thumbnail
大家好,我是woody,是一名料理創作者,非常努力地在嘗試將複雜的料理簡單化,讓大家也可以體驗到料理的樂趣而我也非常享受料理的過程,今天想跟大家聊聊,除了料理本身,料理創作背後的成本。
Thumbnail
哈囉~很久沒跟各位自我介紹一下了~ 大家好~我是爺恩 我是一名圖文插畫家,有追蹤我一段時間的應該有發現爺恩這個品牌經營了好像.....快五年了(汗)時間過得真快!隨著時間過去,創作這件事好像變得更忙碌了,也很開心跟很多厲害的創作者以及廠商互相合作幫忙,還有最重要的是大家的支持與陪伴🥹。  
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
題目敘述 624. Maximum Distance in Arrays 給定一個輸入二維陣列arrays。 請計算的陣列距離是多少? 陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列
Thumbnail
題目敘述: 給定一個傳統手機鍵盤,如圖所示 接著給定一個字串word。 現在讓你重新安排每個字母的所在位置,每個字母可以重新安排到2~9這幾個鍵盤上的位置,每個字母限定只能選擇一個數字鍵去對應。 請問重新安排之後,最少要幾次按鍵才能輸出字串word?
Thumbnail
題目敘述 Most Profit Assigning Work 公司裡有n位員工,m件任務。 每位員工的能力記錄在worker陣列。 每個任務對應的能力要求和獲利紀錄在difficulty 和profit陣列。 不同的員工可以做同樣的任務。 請問怎麼分配任務可以得到整體最大獲利?
Thumbnail
題目敘述 Patching Array 題目給定一個整數陣列, 請問還要補上多少個數字,才能用這些數字的和拼湊出所有1~n的整數。
Thumbnail
題目敘述 題目會給我們一個整數陣列,裡面包含各種正整數,每回合可以消去兩個相同的數字,或者消去三個相同的數字。問最少需要幾次消去,才能讓陣列為空? 如果無解,則返回-1 詳細的題目可在這裡看到 測試範例 Example 1: Input: nums = [2,3,3,2,2,4,2,3,