Leetcode 1338. Reduce Array Size to The Half

Tyan

发布于 2021-07-08 16:23:08

33900

代码可运行

文章被收录于专栏：SnailTyanSnailTyan

运行总次数：0

代码可运行

文章作者：Tyan 博客：noahsnail.com | CSDN | 简书

1. Description

2. Solution

**解析：**对数组中的元素个数进行统计，并按从大到小排列，一次移除一个元素，直至剩余元素个数小于等于移除的元素个数。

Version 1

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        stat = {}
        n = len(arr)
        for num in arr:
            stat[num] = stat.get(num, 0) + 1

        values = sorted(stat.values(), reverse=True)
        count = 0
        size = 0
        for v in values:
            size += 1
            count += v
            thres = count * 2
            if thres >= n:
                break
        return size

Version 2

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        stat = Counter(arr)
        n = len(arr)
        
        values = sorted(stat.values(), reverse=True)
        count = 0
        size = 0
        for v in values:
            size += 1
            count += v
            thres = count * 2
            if thres >= n:
                break
        return size