1338_数组大小减半

类型：数组

• 1338. 数组大小减半 💛

  https://leetcode-cn.com/problems/reduce-array-size-to-the-half/

  ❓ 给你一个整数数组 nums，选定一个最小集合，至少可以囊括数组中一半的元素。返回集合大小。

  💡 哈希表

  统计各个数字出现的次数，存入哈希表。降序排序后，从哈希表中优先取出出现次数多的元素，直到过半。

  class Solution:
      def minSetSize(self, arr: List[int]) -> int:
          freq = collections.Counter(arr)
          cnt, ans = 0, 0
          for num, occ in freq.most_common():
              cnt += occ
              ans += 1
              if cnt * 2 >= len(arr):
                  break
          return ans

  时间复杂度：O(NlogN)，空间复杂度：O(n)