刪除盡可能多的數字 Least Num of Unique after K Remove_Leetcode 1481

Alexander Schimmeck on Unsplash

題目敘述

題目會給我們一個輸入整數陣列arr，和一個初始化的刪除次數k？

我們可以任意選擇從arr中刪除k個陣列元素，請問最後留下來的數字，最少會有幾個不同的數字?

註: 最後不同的數字越少越好。

題目的原文敘述

測試範例

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
刪除一個4

最後只留下5
len( set(5) ) = 1​

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.
刪除一個4
刪除一個2
再任選刪除一個1 或者 一個3
最後者剩下1, 3
len( set(1,3)​ ) = 2

約束條件

Constraints:

• 1 <= arr.length <= 10^5

arr陣列長度介於1~十萬之間。

• 1 <= arr[i] <= 10^9

陣列元素都介於1~十億之間。

• 0 <= k <= arr.length

k值介於0~arr陣列長度 之間。

演算法 Hash table + 出現次數的直方圖 + Greedy

怎麼刪除，才能讓最後不同的數字最少?

有一個基本直覺得想法，先刪除那些烙單或者出現比較少的數字?

為什麼?

因為k值是有限的，必須在k次內盡可能刪掉和別人不一樣的數字。

因此，到這邊有了一個Greedy演算法的想法:

先根據輸入陣列建立每個陣列元素的出現次數統計。

再建立一個關於出現次數的直方圖，每一回合刪除時，都從出現次數最少的開始刪，

一值到刪除次數用完為止。

程式碼 Hash table + 出現次數的直方圖 + Greedy

class Solution:
    def findLeastNumOfUniqueInts(self, arr: List[int], k: int) -> int:
        
        ## Dictionary
        # key: unique array number
        # value: corresponding occurrence
        occurrence = Counter(arr)

        # n = Counting of unique number in input array
        n = len(occurrence)
        
        ## Dictionary
        # key: occurrence
        # value: distribution of occurrence
        histogram = Counter( occurrence.values() )

        ## Greedy stategy
        # Remove unique number as many as possible
        # Remove number from low occurrence to high occurrence
        for occ in range(1, len(arr)+1 ):
            
            if k >= occ * histogram[occ]:
                # We can remove all number with current occurrence
                # Update available removing count
                k -= occ * histogram[occ]

                # Update remaining count of unique numbers
                n -= histogram[occ]
            else:
                # We can only remove part of number with current occurrence
                # k = 0 after this round

                # Update remaining count of unique numbers
                return n - k // occ

        return n

複雜度分析 Hash table + 出現次數的直方圖 + Greedy

時間複雜度:

​建立字典，和迴圈迭代都是一次線性掃描，皆為O(n)

空間複雜度:

字典長度最大為O(n)，最差情況發生再每個數字都不一樣的時候。

關鍵知識點

怎麼刪除，才能讓最後不同的數字最少?

有一個基本直覺得想法，先刪除那些烙單或者出現比較少的數字?

為什麼?

因為k值是有限的，必須在k次內盡可能刪掉和別人不一樣的數字。

Reference:

[1] Least Number of Unique Integers after K Removals - LeetCode