leetcode 1338. Reduce Array Size to The Half(python)
「這是我參與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/
您的支援是我最大的動力
「其他文章」
- 硬肝三千字!位元組跳動發表的中文糾錯模型 Soft-Masked BERT 論文詳解
- 近三千字肝貨!騰訊中文糾錯模型 PLOME 論文詳解!簡單易懂包學包會!
- 2022 年終獎個稅計算方法,看看你被多收割了多少
- leetcode 1537. Get the Maximum Score(python)
- 感謝那段現在回想起來仍然心有餘悸的人生
- leetcode 148. Sort List(python)
- leetcode 1627. Graph Connectivity With Threshold (python)
- leetcode 1616. Split Two Strings to Make Palindrome (python)
- leetcode 147. Insertion Sort List(python)
- leetcode 1611. Minimum One Bit Operations to Make Integers Zero(python)
- leetcode 1606. Find Servers That Handled Most Number of Requests(python)
- leetcode 1610. Maximum Number of Visible Points(python)
- leetcode 1238. Circular Permutation in Binary Representation(python)
- leetcode 1433. Check If a String Can Break Another String(python)
- leetcode 1130. Minimum Cost Tree From Leaf Values(python)
- bisect 庫
- leetcode 889.Construct Binary Tree from Preorder and Postorder Traversal(python)
- leetcode 1338. Reduce Array Size to The Half(python)
- leetcode 406. Queue Reconstruction by Height(python)
- leetcode 1043. Partition Array for Maximum Sum (python)