gpt4 book ai didi

python-3.x - 减少比较连续子数组的时间复杂度?

转载 作者:行者123 更新时间:2023-12-01 02:29:47 25 4
gpt4 key购买 nike

假设我有一个这样的列表序列。

我想删除总和 = N 和/或它有一个总和 = N 的连续子数组的所有序列。

例如,如果 N = 4,则 (1,1,2) 无效,因为它的总数为 4。(1,1,3) 也无效,因为 (1,3) 也是 4。由于同样的原因,(1,3,1) 也是无效的。

lst = [ 
(1,1,1), (1,1,2), (1,1,3),
(1,2,1), (1,2,2), (1,2,3),
(1,3,1), (1,3,2), (1,3,3),
(2,1,1), (2,1,2), (2,1,3),
(2,2,1), (2,2,2), (2,2,3),
(2,3,1), (2,3,2), (2,3,3),
(3,1,1), (3,1,2), (3,1,3),
(3,2,1), (3,2,2), (3,2,3),
(3,3,1), (3,3,2), (3,3,3)
]

例如

Input: 4 3
Output: 2 1 2

所以我现在有的是

lst = [t for t in list(product(range(1,n),repeat=n-1)) if not any((sum(t[l:h+1]) % n == 0) for l, h in combinations(range(len(t)), 2))]

如果我没记错的话,目前它在 O(n2) 中。执行此操作的更好方法是什么?

最佳答案

如果可以使用 numpy,则可以将每个元组的总和与连续值的总和连接起来,然后检查是否有任何结果元素等于 4:

arr = np.array(lst)
arr[~(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),
(arr[:,:-1]+ arr[:,1:])),axis=1) == 4).any(1)]
# or:
arr[(np.concatenate((np.sum(arr,axis=1).reshape(-1,1),
(arr[:,:-1]+ arr[:,1:])),axis=1) != 4).all(1)]

返回:

array([[1, 1, 1],
[1, 2, 3],
[2, 1, 2],
[2, 3, 2],
[2, 3, 3],
[3, 2, 1],
[3, 2, 3],
[3, 3, 2],
[3, 3, 3]])

关于python-3.x - 减少比较连续子数组的时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53384351/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com