python - 缩小输入时的空间复杂度

Question

假设您要查找一个数组中的所有重复项，并且您必须在 O(1) 空间和 O(N) 时间内完成此操作。

像这样的算法会有 O(N) 空间:

def find_duplicates(arr):

    seen = set()
    res = []
    for i in arr:
        if i in seen: res.append(i)
        seen.add(i)
    return res

我的问题是以下算法会使用 O(1) 空间还是 O(N) 空间:

def find_duplicates(arr):

    seen = set()
    res = []
    while arr:
        i = arr.pop()
        if i in seen: res.append(i)
        seen.add(i)
    return res

从技术上讲，arr 变得更小，|seen| 和 |arr| 的总和将始终小于原始 | arr|，但归根结底，我认为它仍在为 seen 分配 |arr| 空间。

Answer 1

为了确定空间复杂度，您必须了解一些关于pop 是如何实现的，以及Python 是如何管理内存的。为了让您的算法使用常量空间，arr 必须释放弹出项目使用的内存，而 seen 必须能够重用该内存。但是，大多数 Python 实现可能不支持这种级别的共享。特别是，pop 不会释放任何内存；它将防止将来需要它的可能性，而不必要求恢复内存。