Python에서 힙을 사용하는 상위 K 단어 [중복]

Question

O (N log K) 시간에 Top K Frequent Words Leetcode 문제 를 해결하려고하는데 원하지 않는 결과가 나타납니다. 내 Python3 코드 및 콘솔 출력은 다음과 같습니다.

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        
        counts = Counter(words)
        print('Word counts:', counts)
        
        result = []
        for word in counts:
            print('Word being added:', word)
            if len(result) < k:
                heapq.heappush(result, (-counts[word], word))
                print(result)
            else:
                heapq.heappushpop(result, (-counts[word], word))
        result = [r[1] for r in result]
        
        return result

----------- Console output -----------

Word counts: Counter({'the': 3, 'is': 3, 'sunny': 2, 'day': 1})
Word being added: the
[(-3, 'the')]
Word being added: day
[(-3, 'the'), (-1, 'day')]
Word being added: is
[(-3, 'is'), (-1, 'day'), (-3, 'the')]
Word being added: sunny
[(-3, 'is'), (-2, 'sunny'), (-3, 'the'), (-1, 'day')]

를 사용하여 테스트 케이스 ["the", "day", "is", "sunny", "the", "the", "sunny", "is", "is"]를 실행하면 둘 다 3의 개수가 추가 되었음에도 한 번 추가 되면 K = 4단어 the가 목록의 끝 (후 day) 으로 이동 한다는 것을 알 수 is있습니다. 부모가 <= 자식 일 필요가 있기 때문입니다. 그리고 아이들은 어떤 식 으로든 주문되지 않습니다. 이후 (-2, 'sunny')및 (-3, 'the')모두> (-3, 'is'), 힙 불변는 사실에도 불구하고 유지 (-3, 'the')< (-2, 'sunny')및 오른쪽 아이입니다 (-3, 'is'). 예상 결과는 ["is","the","sunny","day"]내 코드의 출력이 ["is","sunny","the","day"].

O (N log K) 시간 내에이 문제를 해결하기 위해 힙을 사용해야하며, 그렇다면 원하는 결과를 얻기 위해 코드를 어떻게 수정할 수 있습니까?

Answer 1

당신은 사용하여 올바른 궤도에있어 heapq그리고 Counter당신은 당신이 K의 관계에서 그들을 사용하는 방법에 약간의 수정을해야합니다 (당신은 아무것도를 추가하기 전에 반복 처리 카운트 전체를 필요 result) :

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        counts = collections.Counter(words)
        max_heap = []
        for key, val in counts.items():
            heapq.heappush(max_heap, (-val, key))
        
        result = []
        while k > 0:
            result.append(heapq.heappop(max_heap)[1])
            k -= 1
        
        return result

---

이전에 O (N log k)의 요구 사항을 읽지 않았으며이를 달성하기 위해 위의 솔루션을 수정했습니다.

from collections import Counter, deque
import heapq

class WordWithFrequency(object):
    def __init__(self, word, frequency):
        self.word = word
        self.frequency = frequency

    def __lt__(self, other):
        if self.frequency == other.frequency:
            return lt(other.word, self.word)
        else:
            return lt(self.frequency, other.frequency)

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:    
        counts = collections.Counter(words)
        
        max_heap = []
        for key, val in counts.items():
            heapq.heappush(max_heap, WordWithFrequency(key, val))
            if len(max_heap) > k:
                heapq.heappop(max_heap)
        
        result = deque([]) # can also use a list and just reverse at the end
        while k > 0:
            result.appendleft(heapq.heappop(max_heap).word)
            k -= 1
        
        return list(result)

Answer 2

힙으로 귀찮게 할 필요가 없습니다. Counter ()에는 이미 가장 일반적인 요소를 반환하는 메서드가 있습니다.

>>> c = Counter(["the", "day", "is", "sunny", "the", "the", "sunny", "is", "is"])
>>> c.most_common(4)
[('the', 3), ('is', 3), ('sunny', 2), ('day', 1)]