场景

面试官老王：给你出一道题吧，很简单，统计字符串中各个字符出现的次数

求职者小李：嗯，好的！

( 于是小李开始输出..

1	from collections import Counte...

老王打断小李：emm.. 不，不要用Counter

小李被打断有点慌：啊好的

老王温馨提醒：就用字典吧

小李诧异心想：就这？

( 于是小李又开始输出..

def count(s):
    res = {}
    for i in s:
        if i not in res:
            res[i] = 1
        else:
            res[i] += 1
    print(res)

老王：嗯，好，那你分析一下复杂度吧

小李心想，这有什么好分析的，不就O(n)么？小李十分肯定答：O(N)!

老王：em..还有优化的空间吗？

小李又看了一眼代码，自己嘀咕：必须扫一遍所有字符，那O(N)还能怎么优化，面试官莫不是在搞我？

气氛有点尴尬，小李怎么也想不出来还能怎么优化..

…
…
…

解答

还可以再减少一次对res的查询

先来分析分析最初的写法

def count(s):
    res = {}
    for i in s:
        if i not in res: # 第一次查res
            res[i] = 1
        else:
            res[i] += 1 # 等价于`res[i] = res[i] + 1` 第二次查res
    print(res)

第一种写法：

def count(s):
    res = {}
    for i in s:
        res[i] = res.get(i, 0) + 1 # 只查了一次res
    print(res)

第二种写法：

from collections import defaultdict
def count2(s):
    res = defaultdict(int)
    for i in s:
        res[i] += 1 # 只查了一次res
    print(res)

shaoxyz

扶我起来，我还能再优化一下代码

场景

解答