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

Question

这是极客健忘问题https://practice.geeksforgeeks.org/problems/maximum-distinct-elements-after-removing-k-elements/0的链接

THis是我的密码-

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 2 3 8 21 20 17 1 7 17 12 9 28 10 3 3 14 8 26 13 13 30 30 30 19 28 14 17 2 23 10 22 30 8 9 6 1 24 17 2 21 27 3 21 16 16 16 15 15 15 8 19 7 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)

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

请注意，堆是最小堆，我将其设为准最大堆，并对计数器进行否定。然后，我们只对减少计数器进行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