【LeetCode】692. TopK Frequent Words解題報告(Python)

【LeetCode】692. TopK Frequent Words解題報告(Python)
ラベル:LeetCode
タイトルアドレス:https://leetcode.com/problems/top-k-frequent-words/description/
タイトルの説明:
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: 1. Try to solve it in O(n log k) time and O(n) extra space.
テーマの大意
単語を出現回数で並べ替え,同じ回数であればアルファベット順に並べ,前のk個のみを返す.
解題方法
出現回数が見られる以上,通常は持参したCounterを用いて統計をとる.出現回数順にこれをソートするにはmost_を使用します.common()関数ですが、この関数は出現回数が等しい場合にアルファベット順に並べられません.したがって、ソート関数をカスタマイズする必要があります.

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        count = collections.Counter(words)
        def compare(x, y):
            if x[1] == y[1]:
                return cmp(x[0], y[0])
            else:
                return -cmp(x[1], y[1])
        return [x[0] for x in sorted(count.items(), cmp = compare)[:k]]

もう1つの方法は、ソートです.

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        count = collections.Counter(words)
        candidates = count.keys()
        candidates.sort(key = lambda w: (-count[w], w))
        return candidates[:k]

重要なのは来て、一般的に、私たちはk個の最大の最小の問題を探し出すのはすべて1つのスタックを使ってしたのだと思っています.この問題ではpythonのスタックの使い方を学びました.heapq.heapify(heap)は、線形時間内に1つのリストをスタックに変換することができる.heapq.heappop(heap)は、スタックのスタックトップを直接ポップアップすることができる.heappush(heap,5)スタックに要素を追加します.
heapはlistであり、上記の関数を使用してもlistであることに注意してください.
pythonのスタックのデフォルトは小さなスタックです.大きなスタックを使用する場合は、要素を追加するときにマイナス記号を使用します.

class Solution(object):
    def topKFrequent(self, words, k):
        """
        :type words: List[str]
        :type k: int
        :rtype: List[str]
        """
        count = collections.Counter(words)
        heap = [(-freq, word) for word, freq in count.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in range(k)]

日付
2018年3月14日