3 回答
TA貢獻1895條經驗 獲得超3個贊
每個問題都有時間限制,我認為大約是15秒。據我所知,所有測試用例在驗證時并行運行,如果超過15秒,測試用例將失敗。具有O(n^3)時間復雜度肯定會使測試用例失敗。
TA貢獻1807條經驗 獲得超9個贊
def answer(l):
triples_count=0
p=len(l)
print l
for i in xrange(p-2):
for j in xrange(i+1, p-1):
if l[j] % l[i] == 0:
for k in xrange(j+1, p):
if l[k] % l[j] == 0:
#print l[i], l[j], l[k]
triples_count=triples_count+1
return(triples_count)
TA貢獻1827條經驗 獲得超9個贊
刪除步驟,因為它會更改數字索引的順序,因為其中一個約束說 。l=sorted(l)i < j < k
考慮以下情況:
4 2 1
答案應該是,但您的代碼將返回。01
關于效率,您可以計算每個數字從右側除以多少個數字。對于每個計數,如下所示:1,2,3,4,5,6
1 2 3 4 5 6
5 2 1 0 0 0
對于 ,當你來到 時,已經在緩存的數組中,所以現在你有2個三元組添加到最終答案中。當你來到時,你會得到三胞胎,所以=。1222132+13
時間復雜度:O(n^2)
空間復雜度:O(n)
因為,問題說,我認為你可以走階乘的方式。The elements of l are between 1 and 999999 inclusive
首先收集映射中的所有值計數。
現在,對每個數字進行每個倍數,并將三元組從最后一個添加到第一個。如下圖所示:
triplet_map = {}
map = {}
for every number in array: # from last to first
if number in triplet_map:
triplets += triplet_map(number)
continue
cnt = 0
for(i = number; i < 1000000; i *= number)
if i in map:
if map(i) > 0:
cnt += map(i)
map(number,map(number) + 1)
triplets += cnt
triplet_map(number,cnt)
這樣,它就像每個數字的對數時間。沒有測試這么多,但似乎有效。
添加回答
舉報
