給定一個包含 N 個整數的陣列 A。如果對于任何 Y >0 和 Z>1，X 可以寫成 Y**Z，則 A 中的元素 X 稱為完美元素
1<= N <= 10^5
1<= A[i] <= 10^5
輸入：
2
9
6
輸出
1
9 可以寫成 3^2
def solve(N,A):
count=0
for i in A:
for j in range(1,int(i)//2):
for k in range(1,int(j):
if j**k == int(i):
count=count 1
i = i 1
return count
這種方法可以為我的系統中的任何型別的輸入提供正確的答案，除非它在競爭性編碼 IDE 中讀取錯誤訊息 Time Limit Exceeded 我如何克服這個問題？
uj5u.com熱心網友回復：
您可以嘗試簡單的預處理。首先，根據限制，您需要檢查大約n * 20數字（因為 2 ** 20 > N），所以這O(n)很好，接下來當您處理所有可能的數字時，您可以簡單地將輸入與預處理資料進行比較，如下所示：
def solve(n, a):
MAXN = 10 ** 5 1
is_perfect = [False] * MAXN
for number in range(1, MAXN):
for power in range(2, 20):
if number ** power > MAXN:
break
is_perfect[number**power] = True
counter = 0
for element in a:
if is_perfect[element]:
counter = counter 1
return counter
最終復雜度為O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/463759.html
上一篇：即使使用佇列也無法按廣度搜索
下一篇：有效計算復雜形狀的輪廓