Hướng dẫn 692. top k frequent words python - 692. k từ thường xuyên hàng đầu python

Question

Given a non-empty list of words, return the k most frequent elements.

Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:
Input: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
Output: ["i", "love"]
Explanation: "i" and "love" are the two most frequent words.
    Note that "i" comes before "love" due to a lower alphabetical order.
Example 2:
Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words,
    with the number of occurrence being 4, 3, 2 and 1 respectively.
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Input words contain only lowercase letters.
Follow up:
Try to solve it in O(n log k) time and O(n) extra space.

class Solution:
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        return [w for w, v in sorted(collections.Counter(words).items(), key = lambda x: (-x[1], x[0])) [:k]]

class WordFreq:
    def __init__(self, freq, word):
        self.freq = freq
        self.word = word
        
    def __lt__(self, other):
        if self.freq != other.freq:
            # return self.freq.__lt__(other.freq)
            return self.freq < other.freq
        else:
            # return self.word.__gt__(other.word)
            return self.word > other.word
        
class Solution:
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        counts = collections.Counter(words)   
        
        topk = []
        heapq.heapify(topk)
        for word, freq in counts.items():
            heapq.heappush(topk, WordFreq(freq, word))
            # solution 2: 
            # heapq.heappush(topk, (WordFreq(freq, word), word)) 
            if len(topk) > k:
                heapq.heappop(topk)
        
        res = []
        for _ in range(k):
            res.append(heapq.heappop(topk).word)
            # solution 2: 
            # res.append(heapq.heappop(topk)[1])
        return res[::-1]

struct T {
  string word;
  int freq;
  T(string word, int freq) : word(word), freq(freq) {}
};

class Solution {
 public:
  vector<string> topKFrequent(vector<string>& words, int k) {
    vector<string> ans;
    unordered_map<string, int> count;
    // Words w/ higher frequency and lower alphabetical order are in the bottom
    // Of the heap, because we'll pop words w/ lower frequency and higher
    // Alphabetical order if the heap's size > k
    auto compare = [](const T& a, const T& b) {
      return a.freq == b.freq ? a.word < b.word : a.freq > b.freq;
    };
    priority_queue<T, vector<T>, decltype(compare)> heap(compare);

    for (const string& word : words)
      ++count[word];

    for (const auto& [word, freq] : count) {
      heap.emplace(word, freq);
      if (heap.size() > k)
        heap.pop();
    }

    while (!heap.empty())
      ans.push_back(heap.top().word), heap.pop();

    reverse(begin(ans), end(ans));
    return ans;
  }
};

class T {
  public String word;
  public int freq;
  public T(String word, int freq) {
    this.word = word;
    this.freq = freq;
  }
};

class Solution {
  public List<String> topKFrequent(String[] words, int k) {
    List<String> ans = new ArrayList<>();
    Map<String, Integer> count = new HashMap<>();
    // Words w/ higher frequency and lower alphabetical order are in the bottom
    // Of the heap, because we'll pop words w/ lower frequency and higher
    // Alphabetical order if the heap's size > k

    Queue<T> heap = new PriorityQueue<>(
        (a, b) -> a.freq == b.freq ? b.word.compareTo(a.word) : a.freq - b.freq);

    for (final String word : words)
      count.put(word, count.getOrDefault(word, 0) + 1);

    for (final String word : count.keySet()) {
      heap.offer(new T(word, count.get(word)));
      if (heap.size() > k)
        heap.poll();
    }

    while (!heap.isEmpty())
      ans.add(heap.poll().word);

    Collections.reverse(ans);
    return ans;
  }
}

class T:
  def __init__(self, word: str, freq: int):
    self.word = word
    self.freq = freq

  def __lt__(self, other):
    if self.freq == other.freq:
      # Words w/ higher frequency and lower alphabetical order are in the bottom
      # Of the heap, because we'll pop words w/ lower frequency and higher
      # Alphabetical order if the heap's size > k
      return self.word > other.word
    return self.freq < other.freq


class Solution:
  def topKFrequent(self, words: List[str], k: int) -> List[str]:
    ans = []
    heap = []  # Sorted by freq then alphabet

    for word, freq in Counter(words).items():
      heapq.heappush(heap, T(word, freq))
      if len(heap) > k:
        heapq.heappop(heap)

    while heap:
      ans.append(heapq.heappop(heap).word)

    return ans[::-1]

programming python Leet code Leetcode 451 Easy LeetCode Leetcode python Heap LeetCode LeetCode C#

Hướng dẫn 692. top k frequent words python - 692. k từ thường xuyên hàng đầu python

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội