Leetcode 1481. Least Number of Unique Integers after K Removals

Tyan

发布于 2021-03-02 16:29:22

3080

发布于 2021-03-02 16:29:22

文章被收录于专栏：SnailTyan

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

1. Description

Least Number of Unique Integers after K Removals

2. Solution

Version 1

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        stat = {}
        for num in arr:
            stat[num] = stat.get(num, 0) + 1
        result = sorted(stat.items(), key=lambda item: item[1])
        while k > 0:
            k = k - result[0][1]
            if k >= 0:
                result.pop(0)
        return len(result)

Version 2

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        stat = {}
        for num in arr:
            stat[num] = stat.get(num, 0) + 1
        result = sorted(stat.items(), key=lambda item: item[1])
        index = 0
        while k > 0:
            k = k - result[index][1]
            if k >= 0:
                index += 1
        return len(result) - index

Version 3

class Solution:
    def findLeastNumOfUniqueInts(self, arr, k):
        stat = {}
        for num in arr:
            stat[num] = stat.get(num, 0) + 1
        result = sorted(arr, key=lambda num: (stat[num], num))
        return len(set(result[k:]))