使用以下輸入，[1, 2, 3, 4]我正在嘗試獲得以下輸出[[1], [1, 2], [1, 2, 3], [1, 2, 3, 4], [2], [2, 3], [2, 3, 4], [3], [3, 4], [4]]目前我已經(jīng)做了這樣的算法，但是時(shí)間復(fù)雜度不好。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貢獻(xiàn)1818條經(jīng)驗(yàn) 獲得超3個(gè)贊
連續(xù)子序列
OP 在評(píng)論中指出他們對(duì)連續(xù)的子序列感興趣。
選擇連續(xù)子序列所需的只是選擇起始索引i和結(jié)束索引j。然后我們可以簡(jiǎn)單地返回切片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]]
這個(gè)函數(shù)已經(jīng)在 more_itertools 包中實(shí)現(xiàn)，它被稱為substrings：
import more_itertools
print(list(more_itertools.substrings([0, 1, 2])))
# [(0,), (1,), (2,), (0, 1), (1, 2), (0, 1, 2)]
不連續(xù)的子序列
為了完整性。
查找可迭代對(duì)象的“冪集”是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)]
阿波羅的戰(zhàn)車
TA貢獻(xiàn)1862條經(jīng)驗(yàn) 獲得超6個(gè)贊
您可以簡(jiǎn)單地在一行 ( ) 中使用列表理解來(lái)完成此操作O(N^2)，這比您現(xiàn)有的方法更快：
>>> 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]]
運(yùn)行時(shí)間比較：
# 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貢獻(xiàn)1898條經(jīng)驗(yàn) 獲得超8個(gè)贊
怎么樣：
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貢獻(xiàn)1784條經(jīng)驗(yàn) 獲得超7個(gè)贊
這里的時(shí)間復(fù)雜度是O(N^2)。
我不確定這個(gè)問(wèn)題的時(shí)間復(fù)雜度是否可以進(jìn)一步降低 ?_(ツ)_/?。
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]]
添加回答
舉報(bào)
0/150
提交
取消