时间戳

首页 > 解决方案 > 降低比较连续子阵列的时间复杂度？

python-3.x - 降低比较连续子阵列的时间复杂度？

问题描述

所以说我有一个这样的列表序列。

我想删除其总和 = 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(n 2 ) 中。有什么更好的方法来做到这一点？

标签： python-3.x

解决方案

如果您可以使用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]])

推荐阅读