J'essaie de résoudre le problème Top K Frequent Words Leetcode en temps O (N log K) et j'obtiens un résultat indésirable. Mon code Python3 et la sortie de la console sont ci-dessous:
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')]
Lorsque j'exécute le scénario de test ["the", "day", "is", "sunny", "the", "the", "sunny", "is", "is"] avec K = 4 , je trouve que le mot the est déplacé à la fin de la liste (après day ) une fois is ajouté même s'ils ont tous les deux un nombre de 3. Cela a du sens puisque le parent n'a besoin que d'être <= les enfants et les enfants ne sont pas classés dans en tous cas. Puisque (-2, 'sunny') et (-3, 'the') sont tous les deux> (-3, 'is') , l'invariant de tas est, en fait, maintenu même si (-3, 'the') < (-2, 'sunny') et est le bon enfant de (-3, 'is') . Le résultat attendu est ["is","the","sunny","day"] tandis que la sortie de mon code est ["is","sunny","the","day"] .
Dois-je utiliser des tas pour résoudre ce problème en temps O (N log K), et si oui, comment puis-je modifier mon code pour obtenir le résultat souhaité?
3 Réponses :
Vous êtes sur la bonne voie avec l'utilisation de heapq et Counter vous suffit de modifier légèrement la façon dont vous les utilisez par rapport à k: (vous devez itérer l'ensemble des décomptes avant d'ajouter quoi que ce soit au result ):
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)
Je n'ai pas lu l'exigence d'être O (N log k) auparavant, voici une modification de la solution ci-dessus pour y parvenir:
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
Merci pour votre réponse. En supposant que K <N et tous les éléments des words sont uniques, si vous les poussez tous sur le tas, ne sera-ce pas O (N log N) plutôt que O (N log K)?
Vous n'avez pas besoin de vous embêter avec un tas. Counter () a déjà une méthode pour retourner les éléments les plus courants.
>>> c = Counter(["the", "day", "is", "sunny", "the", "the", "sunny", "is", "is"])
>>> c.most_common(4)
[('the', 3), ('is', 3), ('sunny', 2), ('day', 1)]
+1, mais pour le contexte, la plate-forme OP utilise, Leetcode est pour la préparation des entretiens, et généralement les enquêteurs ne vous permettent pas de bibliothèque de fonctions qui traitent l'aspect central de la question. Par exemple, si un problème n'a rien à voir avec la recherche binaire, je parie que la plupart des intervieweurs vous autoriseraient à utiliser bisect.bisect_left , mais most_common pour cette question, imo, à moins que ce ne soit pour un rôle de spécialiste Python.
@ShashSinha Je n'ai pas réalisé le contexte. D'un autre côté, à l'époque où je faisais des interviews, je posais une question spécifique qui obtenait toujours des réponses longues et compliquées. Un candidat vient de répondre "Je les mettrais en tas". et c'est tout ce que j'avais besoin d'entendre!
At-il la complexité temporelle souhaitée?
@superbrain. Counter utilise un tas pour trouver le n plus grand. Je soupçonne donc qu'il utilise l'algorithme standard N log n, où N est le nombre d'éléments que vous avez, et n est le "Je veux le n le plus grand".
En utilisant Counter() et sort() , cela transmettrait également O(N Log N) :
// Most of headers are already included;
// Can be removed;
#include <iostream>
#include <cstdint>
#include <vector>
#include <string>
#include <unordered_map>
#include <queue>
#include <utility>
// The following block might slightly improve the execution time;
// Can be removed;
static const auto __optimize__ = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
struct Solution {
using ValueType = std::uint_fast16_t;
using Pair = std::pair<std::string, ValueType>;
static const std::vector<std::string> topKFrequent(
const std::vector<std::string>& words,
const ValueType k
) {
std::unordered_map<std::string, ValueType> word_counts;
for (const auto& word : words) {
++word_counts[word];
}
std::priority_queue<Pair, std::vector<Pair>, Comparator> word_freqs;
for (const auto& word_count : word_counts) {
word_freqs.push(word_count);
if (std::size(word_freqs) > k) {
word_freqs.pop();
}
}
std::vector<std::string> k_frequent;
while (!word_freqs.empty()) {
k_frequent.emplace_back(word_freqs.top().first);
word_freqs.pop();
}
std::reverse(std::begin(k_frequent), std::end(k_frequent));
return k_frequent;
}
private:
struct Comparator {
Comparator() {}
~Comparator() {}
const bool operator()(
const Pair& a,
const Pair& b
) {
return a.second > b.second || (a.second == b.second && a.first < b.first);
}
};
};
int main() {
std::vector<std::string> words = {"i", "love", "leetcode", "i", "love", "coding"};
std::vector<std::string> top_k_frequents = Solution().topKFrequent(words, 2);
for (const auto& word : top_k_frequents) {
std::cout << word << "\n";
}
}
Voici une solution Java utilisant PriorityQueue:
class Solution {
public static final List<String> topKFrequent(
final String[] words,
final int k
) {
LinkedList<String> frequentWords = new LinkedList<>();
HashMap<String, Integer> wordsMap = new HashMap<>();
for (int i = 0; i < words.length; i++) {
wordsMap.put(words[i], wordsMap.getOrDefault(words[i], 0) + 1);
}
PriorityQueue<Map.Entry<String, Integer>> wordCounterQueue = new PriorityQueue<>(
(a, b) -> a.getValue() == b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue() -
b.getValue()
);
for (Map.Entry<String, Integer> key : wordsMap.entrySet()) {
wordCounterQueue.offer(key);
if (wordCounterQueue.size() > k) {
wordCounterQueue.poll();
}
}
while (!wordCounterQueue.isEmpty()) {
frequentWords.add(0, wordCounterQueue.poll().getKey());
}
return frequentWords;
}
}
De même avec C ++:
class Solution:
def topKFrequent(self, words, k):
words_countmap = collections.Counter(words)
items = list(words_countmap.items())
items.sort(key=lambda item: (-item[1], item[0]))
return [item[0] for item in items[0:k]]