删除 k 个元素后的最大不同元素

Question

这是 geeksforgeeks 的 link 问题 https://practice.geeksforgeeks.org/problems/maximum-distinct-elements-after-removing-k-elements/0

这是我的代码-

import collections
import heapq
def maxoccur(arr,k):
   c = 0
   d = collections.Counter(arr)
   heap = [(value,key) for key,value in d.items()]
   heapq.heapify(heap)
   while(heap):
     x = heapq.heappop(heap)

     if x[0] == 1:
        c+=1
     elif x[0]>1 and k>0:
        k-=1
        y = x[0]-1
        heapq.heappush(heap,(y,x[1]))
     elif k<=0:
        break
    if k == 0:
        while(heap):
            x = heapq.heappop(heap)
            if x[0] == 1:
               c+=1
    elif k>0:
       c-=k
    
    return c

我的代码有什么问题我在这个测试用例中得到了错误的答案-

输入： 84 47 28 26 24 26 17 13 10 2 3 8 21 20 24 17 1 7 23 17 12 9 28 10 3 21 3 14 8 26 30 13 13 19 30 28 14 17 2 23 10 4 22 30 15 8 1 9 1 15 6 2 21 27 4 3 21 17 2 16 16 15 28 27 6 17 10 14 18 25 16 13 16 15 28 15 15 4 21 8 19 7 9 9 25

它的正确输出是： 27

你的代码的输出是： 25

Answer 1

更简单的方法是基于事实，我们首先可以删除任何出现次数 > 1 的项目而不改变不同的值计数，然后删除一些其余的 - 现在不同的值计数变得更少。

def maxoccur(arr,k):
    lena = len(arr)
    lens = len(set(arr))
    excess = lena - lens
    return lens if excess >= k else max(0, lena - k)

作为作者代码转换的旧答案

请注意，堆是最小堆，我 quasi-maxheap 对计数器取反。然后我们只进行 k （如果可能的话）减少计数器的操作并在堆中寻找其余的。

堆中根本不需要源值，但我懒得改代码了。

import collections
import heapq
def maxoccur(arr,k):
    d = collections.Counter(arr)
    heap = [(-value, key) for key,value in d.items()]
    heapq.heapify(heap)
    while (heap) and (k > 0):
        k -= 1
        x = heapq.heappop(heap)
        if x[0] < -1:
            heapq.heappush(heap,(x[0]+1,x[1]))
    return len(heap)

k = 47
arr = [int(i) for i in '28 26 24 26 17 13 10 2 3 8 21 20 24 17 1 7 23 17 12 9 28 10 3 21 3 14 8 26 30 13 13 19 30 28 14 17 2 23 10 4 22 30 15 8 9 15 6 1 24 17 2 21 27 4 3 21 17 2 16 16 15 28 27 6 17 10 14 18 25 16 13 16 15 28 15 15 4 21 8 19 7 9 9 25'.split()]
print(maxoccur(arr,k))

arr = [5, 7, 5, 5, 1, 2, 2]
k = 3
print(maxoccur(arr,k))

>>>
27
4

删除 k 个元素后的最大不同元素

Maximum distinct elements after removing k elements

algorithm

heap

hash

data-structures

python-3.x