有沒有辦法在 O(n) 中列印給定的長度為 n 的非負整數串列的累積和？
例如，給定一個串列 {3,2,3,12,2}
輸出將是：3 5 5 17 17
我將不得不在一個無界的 ram 中實作這個，所以復雜的結構可能很難做到。
uj5u.com熱心網友回復：
如果您使用 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))
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/374287.html