跳转至

Python#
发布于2020-11-06
上次编辑2021-04-27

内置类型#

Details

内置类型.

数字类型 --- int, float, complex

序列类型 --- list, tuple, range

文本序列类型 --- str

二进制序列类型 --- bytes, bytearray, memoryview

集合类型 --- set, frozenset

set 和 frozenset 的实例提供以下操作：

  • isdisjoint(other) 是否没有相同元素
  • issubset(other) / set <= other 子集判断
  • set < other 真子集判断
  • issuperset(other) / set >= other
  • set > other
  • union(*others) / set | other | ... 并集
  • intersection(*others) / set & other & ... 交集
  • difference(*others) / set - other - ... 返回在 set 中但是不在 others 中的元素集合
  • symmetric_difference(other) / set ^ other 并集减去交集

Note

非运算符版本的 union(), intersection(), difference()，以及 symmetric_difference(), issubset() 和 issuperset() 方法会接受任意可迭代对象作为参数。相比之下，它们所对应的运算符版本则要求其参数为集合。

可用于 set 而不能用于不可变的 frozenset 实例的操作（inplace）：

  • update(*others) / set |= other | ...
  • intersection_update(*others) / set &= other & ...
  • difference_update(*others) / set -= other | ...
  • symmetric_difference_update(other) / set ^= other
  • add(elem)
  • remove(elem) 如果 elem 不存在于集合中则会引发 KeyError
  • discard(elem) 如果元素 elem 存在于集合中则将其移除
  • pop() 从集合中移除并返回任意一个元素，如果集合为空则会引发 KeyError
  • clear() 从集合中移除所有元素

映射类型 --- dict

常用模块及函数#

Details

内置函数 1.

  • abs(x) 绝对值，复数返回模
  • all(iterable) 所有元素为真则返回 True
  • any(iterable) 任一元素为真则返回 True
  • bin(x) 返回前缀为 “0b” 的二进制字符串
  • oct(x) 返回前缀为 “0xo” 八进制字符串
  • hex(x) 返回前缀为 “0x” 十六进制字符串
  • chr(i) 整数转字符
  • ord(c) 字符转整数
  • divmod(a, b) 返回商和余数
  • enumerate(iterable, start=0) 添加元素计数
  • range(start, stop[, step])
  • filter(function, iterable) 创建迭代器，得到 iterable 中 function 计算为真的元素
  • map(function, iterable, ...) 返回一个将 function 应用于 iterable 中每一项并输出其结果的迭代器
  • zip(*iterables)
  • float([x]) 返回从数字或字符串 x 生成的浮点数
  • int(x, base=10)
  • len(s) 对象中元素的个数
  • list([iterable])
  • set([iterable])
  • max(arg1, arg2, *args[, key])
  • min(arg1, arg2, *args[, key])
  • sum(iterable, /, start=0)
  • round(number[, ndigits]) 返回 number 舍入到小数点后 ndigits 位精度的值
  • sorted(iterable, *, key=None, reverse=False)

数学运算 2.

  • math.ceil(x) 向上取整
  • math.comb(n, k) 组合数 3.8 新版功能
  • math.factorial(x) 阶乘
  • math.floor(x) 向下取整
  • math.gcd(a, b)
  • math.perm(n, k=None) 排列数 3.8 新版功能
  • math.prod(iterable, *, start=1) 连乘 3.8 新版功能
  • math.log(x[, base]) 默认为自然对数，即底为 \(e\)
  • math.log2(x) 返回以 2 为底的对数，文档中说比 log(x, 2) 更准确
  • math.log10(x) 返回以 10 为底的对数，文档中说比 log(x, 10) 更准确
  • 三角函数
  • 双曲函数

二分查找 3.

优先队列 4.

相关容器 5.

  • collections.Counter 元素计数
  • collections.deque 双端队列
  • collections.defaultdict 默认值字典

高效迭代 6.

  • itertools.accumulate 创建迭代器，累积运算，保留中间的每一步，自定义累积函数，默认为累积和

高阶函数和可调用对象上的操作 7.

  • functools.lru_cache 缓存函数结果，如果遇到同样的参数直接返回结果
  • functools.reduce 累积运算，只返回最后的结果，而 itertools.accumulate 保留中间结果

时间复杂度#

下面列出了基于 CPython 实现的常用数据结构的相关操作的时间复杂度 8。

表中的 \(n\) 表示容器中元素的数量，\(k\) 是参数的值或参数中元素的数量。

Details
操作 平均时间复杂度 最差时间复杂度
Copy \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Append \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
Pop last \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
Pop intermediate \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Insert \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Get Item \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
Set Item \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
Delete Item \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Iteration \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Get Slice \(\mathcal{O}(k)\) \(\mathcal{O}(k)\)
Del Slice \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Set Slice \(\mathcal{O}(k+n)\) \(\mathcal{O}(k+n)\)
Extend \(\mathcal{O}(k)\) \(\mathcal{O}(k)\)
Sort \(\mathcal{O}(n\log n)\) \(\mathcal{O}(n\log n)\)
Multiply \(\mathcal{O}(nk)\) \(\mathcal{O}(nk)\)
x in s \(\mathcal{O}(n)\)
min(s), max(s) \(\mathcal{O}(n)\)
Get Length \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
操作 平均时间复杂度 最差时间复杂度
Copy \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
append \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
appendleft \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
pop \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
popleft \(\mathcal{O}(1)\) \(\mathcal{O}(1)\)
extend \(\mathcal{O}(k)\) \(\mathcal{O}(k)\)
extendleft \(\mathcal{O}(k)\) \(\mathcal{O}(k)\)
rotate \(\mathcal{O}(k)\) \(\mathcal{O}(k)\)
remove \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
操作 平均时间复杂度 最差时间复杂度
x in s \(\mathcal{O}(1)\) \(\mathcal{O}(n)\)
Union s|t \(\mathcal{O}(\text{len}(s)+\text{len}(t))\)
Intersection s&t \(\mathcal{O}(\min(\text{len}(s),\text{len}(t)))\) \(\mathcal{O}(\text{len}(s)\times\text{len}(t))\)
Multiple intersection s1&s2&..&sn \((n-1)\times\mathcal{O}(\max(\text{len}s_i))\)
Difference s-t \(\mathcal{O}(\text{len}(s))\)
s.difference_update(t) \(\mathcal{O}(\text{len}(t))\)
Symmetric Difference s^t \(\mathcal{O}(\text{len}(s))\) \(\mathcal{O}(\text{len}(s)\times\text{len}(t))\)
s.symmetric_difference_update(t) \(\mathcal{O}(\text{len}(t))\) \(\mathcal{O}(\text{len}(t)\times\text{len}(s))\)
操作 平均时间复杂度 最差时间复杂度
k in d \(\mathcal{O}(1)\) \(\mathcal{O}(n)\)
Copy \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)
Get Item \(\mathcal{O}(1)\) \(\mathcal{O}(n)\)
Set Item \(\mathcal{O}(1)\) \(\mathcal{O}(n)\)
Delete Item \(\mathcal{O}(1)\) \(\mathcal{O}(n)\)
Iteration \(\mathcal{O}(n)\) \(\mathcal{O}(n)\)

高效操作#

数据读取

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import sys
from typing import List

readline = sys.stdin.readline


def readint() -> int:
    return int(readline().strip())


def readstr() -> str:
    return readline().strip()


def readints() -> List[int]:
    return list(map(int, readline().strip().split()))

元素的插入与删除

当需要在在 list 中插入或删除数据，下面的代码速度很快：

1
2
3
4
5
6
7
8
9
def insert(nums: List[int], k: int, val: int):
    # 在 nums 第 k 个位置处插入 val
    nums[k:k] = [val]


def delete(nums: List[int], k: int):
    # 删除 nums[k]
    nums[k : k + 1] = []
    del nums[k]  # 这个速度好像也很快

这种方法在需要 维护一个有序数组时非常非常有用，一般会与 bisect 库结合使用。

数组差分

1
list(map(lambda x: x[1] - x[0], zip(nums[:-1], nums[1:])))

前缀和

1
list(accumulate(nums))

反向遍历

Python 切片操作的时间复杂度是 \(\mathcal{O}(k)\)，\(k\) 是切片大小，如 s[::-1] 的时间复杂度是 \(\mathcal{O}(n)\)。

所以如果需要反向遍历列表，不要使用 for x in s[::-1]，可以使用 for x in reversed(s)，reversed 返回的是一个迭代器。

在遍历切片时，也可以使用下标操作。

排序#

Python 中的排序 9 可以使用 list 自带的 sort 方法或者内置函数 sorted，前者会进行原地排序，后者会返回排序后的列表而不会改变传入列表。

  • list.sort
  • sorted

它们都可以使用关键词 key 来自定义排序规则，但是这个自定义的排序函数只接受单个参数，即元素本身。如果判断两个元素的顺序需要根据两个元素的组合的先后顺序判断，则可以把比较函数作为 functools.cmp_to_key 的参数传递给关键字 key。

如对于 179. 最大数 和 剑指 Offer 45. 把数组排成最小的数，就需要使用两个元素进行比较。

注意事项#

list.sort

CPython implementation detail: 10 在一个列表被排序期间，尝试改变甚至进行检测也会造成未定义的影响。 Python 的 C 实现会在排序期间将列表显示为空，如果发现列表在排序期间被改变将会引发 ValueError。

例如不能直接在排序的过程中使用 nums.count(x)。

  1. https://docs.python.org/zh-cn/3/library/functions.html ↩

  2. https://docs.python.org/zh-cn/3/library/math.html ↩

  3. https://docs.python.org/zh-cn/3/library/bisect.html ↩

  4. https://docs.python.org/zh-cn/3/library/heapq.html ↩

  5. https://docs.python.org/zh-cn/3/library/collections.html ↩

  6. https://docs.python.org/zh-cn/3/library/itertools.html ↩

  7. https://docs.python.org/zh-cn/3/library/functools.html ↩

  8. https://wiki.python.org/moin/TimeComplexity ↩

  9. 排序指南 ↩

  10. https://docs.python.org/zh-cn/3/library/stdtypes.html#list.sort ↩

返回顶部

在手机上阅读