使用以下输入，[1, 2, 3, 4]我正在尝试获得以下输出[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]目前我已经做了这样的算法，但是时间复杂度不好。def find(height): num1 = 0 out = [] for i in range(len(height)): num2 = 1 for j in range(len(height)): temp = [] for x in range(num1, num2): temp.append(height[x]) num2 += 1 if temp: out.append(temp) num1 += 1 return out有什么办法可以加速该算法吗？
4 回答
泛舟湖上清波郎朗
TA贡献1818条经验 获得超3个赞
连续子序列
OP 在评论中指出他们对连续的子序列感兴趣。
选择连续子序列所需的只是选择起始索引i和结束索引j。然后我们可以简单地返回切片l[i:j]。
def contiguous_subsequences(l):
return [l[i:j] for i in range(0, len(l)) for j in range(i+1, len(l)+1)]
print(contiguous_subsequences([1,2,3,4]))
# [[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]
这个函数已经在 more_itertools 包中实现，它被称为substrings：
import more_itertools
print(list(more_itertools.substrings([0, 1, 2])))
# [(0,), (1,), (2,), (0, 1), (1, 2), (0, 1, 2)]
不连续的子序列
为了完整性。
查找可迭代对象的“幂集”是itertool 的秘诀：
import itertools
def powerset(iterable):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
return itertools.chain.from_iterable(itertools.combinations(s, r) for r in range(len(s)+1))
它也在包more_itertools中：
import more_itertools
print(list(more_itertools.powerset([1,2,3,4])))
# [(), (1,), (2,), (3,), (4,), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), (1, 2, 3, 4)]
阿波罗的战车
TA贡献1862条经验 获得超6个赞
您可以简单地在一行 ( ) 中使用列表理解来完成此操作O(N^2)，这比您现有的方法更快：
>>> x = [1,2,3,4]
>>> [x[i:j] for i in range(len(x)) for j in range(i+1,len(x)+1)]
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]
运行时间比较：
# your solution
>>> %timeit find(x)
9.23 µs ± 445 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#itertools method suggested by 'stef'
>>> %timeit list(more_itertools.substrings([1, 2, 3,4]))
3.18 µs ± 20.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
#List comprehension method
>>> %timeit [x[i:j] for i in range(len(x)) for j in range(i+1,len(x)+1)]
3.09 µs ± 27.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
汪汪一只猫
TA贡献1898条经验 获得超8个赞
怎么样：
a = [1, 2, 3, 4]
l = len(a)
ret = []
for i in range(l):
ll = i + 1
while ll <= l:
ret.append(a[i:ll])
ll +=1
print(ret)
印刷：
[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]
噜噜哒
TA贡献1784条经验 获得超7个赞
这里的时间复杂度是O(N^2)。
我不确定这个问题的时间复杂度是否可以进一步降低 ́_(ツ)_/̊。
def find(arr):
d = {}
d[0] = []
i = 1
while (i <= len(arr)):
d[i] = [] + d[i - 1]
val = arr[i - 1]
j = i - 1
l = len(d[i - 1])
while (j > 0):
d[i].append(d[i - 1][l - j] + [val])
j = j - 1
d[i].append([val])
i = i + 1
return d[len(arr)]
input = [1, 2, 3, 4]
print(find(input))
输出：
[[1], [1, 2], [2], [1, 2, 3], [2, 3], [3], [1, 2, 3, 4], [2, 3, 4], [3, 4], [4]]
添加回答
举报
0/150
提交
取消