leetcode 1338. Reduce Array Size to The Half（python）_王大呀呀

leetcode 1338. Reduce Array Size to The Half（python）

語言: CN / TW / HK

「這是我參與11月更文挑戰的第20天，活動詳情檢視：2021最後一次更文挑戰」

描述

You are given an integer array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.

Return the minimum size of the set so that at least half of the integers of the array are removed.

Example 1:

Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.

Example 2:

Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

Example 3:

Input: arr = [1,9]
Output: 1

Example 4:

Input: arr = [1000,1000,3,7]
Output: 1

Example 5:

Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5

Note:

1 <= arr.length <= 10^5
arr.length is even.
1 <= arr[i] <= 10^5

解析

根據題意，給定一個整數陣列 arr。可以從中選擇一組整數並刪除陣列中出現過的所有這些整數。題目要求我們返回最小集合的大小，以便刪除陣列中至少一半的整數。看題目中的條件限制有點懵，已經明確告訴 arr.length 是偶數，但是又說 arr.length 大於等於 1 小於等於 10^5 ，are you kiding ？是我數學沒學好嗎 1 怎麼能是偶數呢？

思路比較簡單：

初始化結果 result 為 0 ，L 為 arr 長度的一半，使用內建函式 Counter 對 arr 進行計數
對計數結果按照 value 降序排列，遍歷所有的鍵值對，只要 L 還大於 0 就 result 加一，同時 L 減 value ，迴圈這個過程直到 break ，這樣能移除最少的數字實現刪除一半以上的整數
最後返回 result

解答

class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        c = collections.Counter(arr)
        L = len(arr)//2
        result = 0
        for k,v in sorted(c.items(), key=lambda x:-x[1]):
            if L>0:
                result += 1
                L -= v
            else:
                break
        return result

執行結果

Runtime: 640 ms, faster than 52.86% of Python online submissions for Reduce Array Size to The Half.
Memory Usage: 37.3 MB, less than 35.71% of Python online submissions for Reduce Array Size to The Half.

原題連結：http://leetcode.com/problems/reduce-array-size-to-the-half/

您的支援是我最大的動力