列表的累积和忽略 O(n) 中的重复元素

Question

有没有办法在 O(n) 中打印给定长度为 n 的非负整数列表的累加和？

例如，给定一个列表 {3,2,3,12,2}

输出将是：3 5 5 17 17

我必须在无界 ram 中实现它，所以复杂的结构可能很难做到。

Answer 1

如果你使用 HashSet 来查找已经看到的元素，那么你只需要一次传递就可以在 O(n).

中解决这个问题

def cumulative_sum(l):
    seen = set()
    result = []
    for e in l:
        last = result[-1] if result else 0
        if e in seen:
            result.append(last)
        else:
            seen.add(e)
            result.append(last + e)
    return result

l = [3, 2, 3, 12, 2]
print(cumulative_sum(l))

列表的累积和忽略 O(n) 中的重复元素

cumulative sum of list ignoring duplicated elements in O(n)

algorithm

time-complexity

cumulative-sum