Top K Häufige Wörter mit Heaps in Python [Duplikat]

Question

Ich versuche, das Leetcode-Problem mit den häufigsten K-Wörtern in O (N log K) zu lösen, und erhalte ein unerwünschtes Ergebnis. Mein Python3-Code und meine Konsolenausgabe sind unten aufgeführt:

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')]

Wenn ich den Testfall ["the", "day", "is", "sunny", "the", "the", "sunny", "is", "is"]mit ausführe, stelle K = 4ich fest, dass das Wort thean das Ende der Liste verschoben wird (nachdem day) einmal ishinzugefügt wurde, obwohl beide eine Anzahl von 3 haben. Dies ist sinnvoll, da die Eltern nur <= die Kinder sein müssen und die Kinder werden in keiner Weise bestellt. Da (-2, 'sunny')und (-3, 'the')beide> sind (-3, 'is'), wird die Heap-Invariante tatsächlich beibehalten, obwohl (-3, 'the')< (-2, 'sunny')und das richtige Kind von ist (-3, 'is'). Das erwartete Ergebnis ist, ["is","the","sunny","day"]während die Ausgabe meines Codes ist ["is","sunny","the","day"].

Sollte ich Heaps verwenden, um dieses Problem in O (N log K) zu lösen, und wenn ja, wie kann ich meinen Code ändern, um das gewünschte Ergebnis zu erzielen?

Answer 1

Sie sind mit der Verwendung auf dem richtigen Weg heapqund Countermüssen nur eine geringfügige Änderung in der Art und Weise vornehmen, wie Sie sie in Bezug auf k verwenden: (Sie müssen die gesamten Zählungen wiederholen, bevor Sie etwas hinzufügen 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

---

Ich habe die Anforderung, O (N log k) zu sein, noch nicht gelesen. Hier ist eine Modifikation der obigen Lösung, um dies zu erreichen:

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

Sie müssen sich nicht um einen Haufen kümmern. Counter () verfügt bereits über eine Methode, um die häufigsten Elemente zurückzugeben.

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