頻度カウントとグループ化

頻度カウント：基本パターン

from collections import Counter

words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple']
freq  = Counter(words)
print(freq)                  # Counter({'apple':3,'banana':2,'cherry':1})
print(freq['apple'])         # 3
print(freq['grape'])         # 0 (not KeyError)
print(freq.most_common(2))   # [('apple',3),('banana',2)]

有効なアナグラム（LeetCode 242）

from collections import Counter

def isAnagram(s, t):
    return Counter(s) == Counter(t)

# Alternative: manual frequency array for lowercase letters only
def isAnagram_arr(s, t):
    if len(s) != len(t):
        return False
    freq = [0] * 26
    for c in s: freq[ord(c) - ord('a')] += 1
    for c in t: freq[ord(c) - ord('a')] -= 1
    return all(f == 0 for f in freq)

print(isAnagram('anagram', 'nagaram'))  # True
print(isAnagram('rat', 'car'))          # False
print(isAnagram_arr('listen', 'silent'))  # True

アナグラムのグループ化（LeetCode 49）

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(sorted(s))   # hashable canonical form
        groups[key].append(s)
    return list(groups.values())

print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

# Alternative key: tuple of 26 character counts (O(L) not O(L log L))
def groupAnagrams_v2(strs):
    groups = defaultdict(list)
    for s in strs:
        key = tuple(ord(c) - ord('a') for c in sorted(s))
        groups[tuple(Counter(s)[chr(ord('a')+i)] for i in range(26))].append(s)
    return list(groups.values())

頻度の高い上位 K 個の要素（LeetCode 347）

from collections import Counter

def topKFrequent(nums, k):
    freq  = Counter(nums)
    # Bucket sort by frequency
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, count in freq.items():
        buckets[count].append(num)
    result = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]
    return result

print(topKFrequent([1,1,1,2,2,3], 2))  # [1, 2]
print(topKFrequent([1], 1))             # [1]

頻度順に文字を並べ替える（LeetCode 451）

from collections import Counter

def frequencySort(s):
    freq = Counter(s)
    return ''.join(ch * count for ch, count in freq.most_common())

print(frequencySort('tree'))    # 'eetr' or 'eert'
print(frequencySort('cccaaa'))  # 'cccaaa' or 'aaaccc'
print(frequencySort('Aabb'))    # 'bbAa' or 'bbaA'

タスクスケジューラ（LeetCode 621）

from collections import Counter

def leastInterval(tasks, n):
    freq      = Counter(tasks)
    max_count = max(freq.values())
    # How many tasks share the max frequency
    num_max   = sum(1 for v in freq.values() if v == max_count)
    # Minimum slots needed based on most frequent task
    min_slots = (max_count - 1) * (n + 1) + num_max
    return max(min_slots, len(tasks))

print(leastInterval(['A','A','A','B','B','B'], 2))  # 8
print(leastInterval(['A','A','A','B','B','B'], 0))  # 6
print(leastInterval(['A','A','A','A','B','B','B','C','C','D'], 2))  # 10

Counter による過半数判定

from collections import Counter

def majorityElement_counter(nums):
    freq = Counter(nums)
    return freq.most_common(1)[0][0]

# Boyer-Moore O(1) space
def majorityElement_moore(nums):
    candidate, count = None, 0
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

nums = [2, 2, 1, 1, 2, 2, 2]
print(majorityElement_counter(nums))  # 2
print(majorityElement_moore(nums))    # 2

最初の重複しない文字

from collections import Counter

def firstUniqChar(s):
    freq = Counter(s)
    for i, ch in enumerate(s):
        if freq[ch] == 1:
            return i
    return -1

print(firstUniqChar('leetcode'))   # 0 (l)
print(firstUniqChar('loveleetcode'))  # 2 (v)
print(firstUniqChar('aabb'))       # -1

部分配列の合計が K（LeetCode 560）

from collections import defaultdict

def subarraySum(nums, k):
    freq         = defaultdict(int)
    freq[0]      = 1   # prefix sum of 0 seen once (empty prefix)
    prefix_sum   = 0
    count        = 0
    for num in nums:
        prefix_sum += num
        # How many earlier prefix sums allow a k-sum subarray ending here
        count      += freq[prefix_sum - k]
        freq[prefix_sum] += 1
    return count

print(subarraySum([1, 1, 1], 2))            # 2
print(subarraySum([1, 2, 3], 3))            # 2
print(subarraySum([1, -1, 1, -1, 1], 0))   # 4

Counter の算術演算と共通部分

from collections import Counter

A = Counter('abccdd')
B = Counter('ccdde')

print('Add:      ', dict(A + B))  # sum of counts
print('Subtract: ', dict(A - B))  # A - B, clipped at 0
print('Intersect:', dict(A & B))  # min of shared counts
print('Union:    ', dict(A | B))  # max counts

# Min steps to make s anagram of t (LeetCode 1347)
s, t = 'leetcode', 'practice'
diff = Counter(t) - Counter(s)
print('Chars to add:', sum(diff.values()))  # 5

まとめ：頻度カウントを使う場面

理解度チェック

レッスンのまとめ