3 posts tagged with "Counting"

import heapq
from collections import Counter
from itertools import chain, islice


class Solution:  # O(n) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        buckets = [[] for _ in nums]
        for n, c in Counter(nums).items():
            buckets[-c].append(n)
        return list(islice(chain.from_iterable(buckets), k))


class Solution1:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [heapq.heappop(heap)[1] for _ in range(k)]


class Solution2:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        heap = []
        for n, c in Counter(nums).items():
            heapq.heappush(heap, (-c, n))
        return [x[1] for x in heapq.nsmallest(k, heap)]


class Solution3:  # O(nlogn) / O(n)
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        return [n for n, _ in Counter(nums).most_common(k)]

import heapq
from collections import Counter


class Solution1:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        c = Counter(words)
        return [x for x in sorted(c, key=lambda key: (-c[key], key))][:k]


class Solution:
    def topKFrequent(self, words: list[str], k: int) -> list[str]:
        c = Counter(words)
        return heapq.nsmallest(k, c, key=lambda key: (-c[key], key))

from collections import Counter


class Solution:
    def getHint(self, s: str, g: str) -> str:
        a, b = 0, 0
        cs, cg = Counter(), Counter()
        for i in range(len(s)):
            if s[i] == g[i]:
                a += 1
                continue
            if cg[s[i]]:
                cg[s[i]] -= 1
                b += 1
            else:
                cs[s[i]] += 1
            if cs[g[i]]:
                cs[g[i]] -= 1
                b += 1
            else:
                cg[g[i]] += 1
        return f'{a}A{b}B'