时间戳

首页 > 解决方案 > K 移除挑战后唯一整数的最少数量

python - K 移除挑战后唯一整数的最少数量

问题描述

挑战如下：

Given an array of integers arr and an integer k. Find the least number of unique integers 
after removing exactly k elements.


Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.
Example 2:
Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.


Constraints:

1 <= arr.length <= 10^5
1 <= arr[i] <= 10^9
0 <= k <= arr.length

我很难理解一个人对此的解决方案。有人愿意解释他的最佳解决方案是如何工作的吗？这是一个新的挑战，在最近的 leetcode 竞赛中，没有重复。

    def findLeastNumOfUniqueInts3(self, A, K):
        count = collections.Counter(A)
        items = list(count.items())
        items.sort(key=lambda e: e[1])
        ans = len(items)
        for i, (_, x) in enumerate(items):
            if K >= x:
                K -= x
                ans -= 1
        return ans

标签： pythonpython-3.xcollectionsdynamic-programming

解决方案

首先，此人使用 Counter(collections) 对数字进行单独计数

假设您的输入列表是 [4,3,1,1,3,3,2]，那么该列表的单个计数变为：

number     count
  4    ->    1
  3    ->    3
  1    ->    2
  2    ->    1

排序后：

number     count
  4    ->    1
  2    ->    1
  1    ->    2
  3    ->    3

现在您可以删除 K 个数字，以获得最少数量的唯一数字，这里的直觉是，我们首先从出现次数最少的数字开始，这样我们就可以删除最大唯一数字，从而产生最少唯一数字（这是所需的）。

现在他遍历项目计数的排序列表，如果当前项目的计数小于 K，则推导出 K 的值，他遍历直到 K==0 或者我们遍历整个列表。如果一个项目的计数小于 K，我们可以增加计数，并可以从给定列表中唯一数字的长度推断它。

这是我的解决方案：

from collections import defaultdict 

def uns(A, K):
    icounts = defaultdict(lambda:0)
    for x in A:
        icounts[x]+=1

    counts = [icounts[i] for i in icounts]
    counts = sorted(counts)

    rem = 0
    for x in counts:
        if K>=x:
            rem+=1
            K-=x
        if(K==0):
            break

    return len(counts)-rem
print(uns([4,3,1,1,3,3,2],3))

输出：

2

希望你能理解我的解释。

推荐阅读