關于這個任務已經有一個話題了，但是我想問一下我的具體做法。任務是：
令 A 為由 N 個整陣列成的非空陣列。
一對索引 (P, Q) 的絕對值和是絕對值 |A[P] A[Q]|，對于 0 ≤ P ≤ Q < N。
例如下面的陣列 A：
A[0] = 1 A 1 = 4 A[2] = -3 具有成對的索引 (0, 0), (0, 1), (0, 2), (1, 1), (1, 2) , (2, 2)。對 (0, 0) 的兩個的絕對和為 A[0] A[0] = |1 1| = 2. (0, 1) 對的兩個的絕對和為 A[0] A 1 = |1 4| = 5. (0, 2) 對的兩個的絕對和為 A[0] A[2] = |1 (?3)| = 2. (1, 1) 對的兩個的絕對和是 A 1 A 1 = |4 4| = 8. 對 (1, 2) 的兩個的絕對和是 A 1 A[2] = |4 (?3)| = 1. 對 (2, 2) 的兩個的絕對和為 A[2] A[2] = |(?3) (?3)| = 6. 寫一個函式：
定義解決方案（A）
即，給定一個由 N 個整陣列成的非空陣列 A，回傳此陣列中任何一對索引的 2 的最小絕對和。
例如，給定以下陣列 A：
A[0] = 1 A 1 = 4 A[2] = -3 該函式應回傳 1，如上所述。
給定陣列 A：
A[0] = -8 A 1 = 4 A[2] = 5 A[3] =-10 A[4] = 3 函式應該回傳 |(?8) 5| = 3。
為以下假設撰寫一個有效的演算法：
N 是 [1..100,000] 范圍內的整數；陣列 A 的每個元素都是 [?1,000,000,000..1,000,000,000] 范圍內的整數。
官方的解決方案是O(N*M^2)，但我認為可以用O(N)解決。我的方法是首先去除重復項并對陣列進行排序。然后我們檢查兩端并計算絕對和，將兩端移向彼此。我們嘗試移動左端、右端或兩者。如果這不能改善結果，我們的總和是最低的。我的代碼是：
def solution(A):
A = list(set(A))
n = len(A)
A.sort()
beg = 0
end = n - 1
min_sum = abs(A[beg] A[end])
while True:
min_left = abs(A[beg 1] A[end]) if beg 1 < n else float('inf')
min_right = abs(A[beg] A[end-1]) if end-1 >= 0 else float('inf')
min_both = abs(A[beg 1] A[end-1]) if beg 1 < n and end-1 >= 0 else float('inf')
min_all = min([min_left, min_right, min_both])
if min_sum <= min_all:
return min_sum
if min_left == min_all:
beg = 1
min_sum = min_left
elif min_right == min_all:
end -= 1
min_sum = min_right
else:
beg = 1
end -= 1
min_sum = min_both
它通過了幾乎所有的測驗，但不是全部。我的代碼中是否存在一些錯誤或方法錯誤？
編輯： 在 aka.nice 回答之后，我能夠修復代碼。現在評分100%。
def solution(A):
A = list(set(A))
n = len(A)
A.sort()
beg = 0
end = n - 1
min_sum = abs(A[beg] A[end])
while beg <= end:
min_left = abs(A[beg 1] A[end]) if beg 1 < n else float('inf')
min_right = abs(A[beg] A[end-1]) if end-1 >= 0 else float('inf')
min_all = min(min_left, min_right)
if min_all < min_sum:
min_sum = min_all
if min_left <= min_all:
beg = 1
else:
end -= 1
return min_sum
uj5u.com熱心網友回復：
以陣列 A 為例
-11 -5 -2 5 6 8 12
并逐步執行你的演算法，你會得到一個過早的回報：
beg=0
end=6
min_sum=1
min_left=7
min_right=3
min_both=3
min_all=3
return min_sum
雖然有更好的解決方案 abs(5-5)=0。
提示：你應該檢查 A[beg] 和 A[end] 的符號來決定是繼續還是退出回圈。如果兩者都 >= 0，如果兩者都 <= 0，否則該怎么辦？
請注意，它A.sort()具有不可忽略的成本，很可能O(N*log(N))它將主導您展示的解決方案的成本。
順便問一下，M官方費用是O(N*M^2)多少？
您提供的鏈接是另一個問題（將 A 的所有元素或相反的元素相加）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482732.html
標籤：算法
上一篇：我如何實際洗掉節點？