我正在嘗試使用遞回來解決 Codility 中的 OddOccurrencesInArray 問題，其中
- 我們得到一個包含 N 個元素的陣列，N 總是奇數
- 陣列中除一個之外的所有元素總共出現偶數次
- 我們需要撰寫回傳一個未配對值的代碼
例如，如果給定的陣列是 [9, 3, 9, 3, 7, 9, 9]，則代碼必須回傳 7，因為這是陣列中唯一不成對的元素。
我的解決方案偽代碼/思考程序是：
- 對陣列進行排序
- 如果前兩個元素彼此相等，則洗掉它們并在減去前兩個元素的陣列上再次遞回運行求解演算法（排序后），即如果未找到未配對的元素，我們將繼續減小陣列的大小
- 如果前兩個元素不相等，則陣列的第一個元素必須是未配對項
我的實作是：
def solution(A):
# write your code in Python 3.6
if len(A) > 1:
A = sorted(A)
if A[0] != A[1]:
return A[0]
else:
solution(A[2:])
else:
return A[0]
我不斷收到錯誤訊息
無效的結果型別，應為 int，找到 <class 'NoneType'>。RUNTIME ERROR（測驗程式以退出代碼 1 終止）
誰能幫我弄清楚這意味著什么以及如何糾正它？從演算法上講，我認為我的解決方案是合理的，但我不明白為什么它沒有回傳我指定的整數值。
uj5u.com熱心網友回復：
您不會從遞回呼叫中回傳任何內容，這意味著您正在回傳None.
uj5u.com熱心網友回復：
我會建議完全不同的方法。遞回方法不是不正確的，但是重復呼叫sorted效率非常低，尤其是在輸入非常大的情況下。
def solve(t):
s = set()
for v in t:
s.add(v) if v not in s else s.remove(v)
return list(s)
input = [9, 3, 9, 3, 7, 9, 9]
solve(input)
我們可以s在評估程序中可視化-
{} # <- initial s
{9} # <- 9 is added
{9,3} # <- 3 is added
{3} # <- 9 is removed
{} # <- 3 is removed
{7} # <- 7 is added
{7,9} # <- 9 is added
{7} # <- 9 is removed
finallylist(s)回傳轉換{7}為[7]. 要輸出答案，我們可以寫一個簡單的if/elif/else-
unpaired = solve(input)
if (len(unpaired) < 1):
print("there are no unpaired elements")
elif (len(unpaired) > 1):
print("there is more than one unpaired element")
else:
print("answer:", unpaired[0])
另一種選擇是solve回傳第一個未配對的元素或None-
def solve(t):
s = set()
for v in t:
s.add(v) if v not in s else s.remove(v)
for v in s:
return v # <- immediately return first element
answer = solve(input)
if answer is None:
print("no solution")
else:
print("the solution is", answer)
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/405883.html
標籤：
下一篇：遞回物件的遞回搜索