給定一個整數陣列（可能包括重復的整數），確定是否有辦法將陣列拆分為兩個子序列 A 和 B，使得兩個陣列中的整數之和相同，并且 A 中的所有整數都是嚴格小于 B 中的所有整數。
示例 1
arr = [1, 5, 7, 1] 輸出 = true
我們可以將陣列拆分為 A = [1, 1, 5] 和 B = [7]。
示例 2
arr = [12, 7, 6, 7, 6] 輸出 = 假
我們不能將陣列拆分為 A = [6, 6, 7] 和 B = [7, 12]，因為這不能滿足 A 中的所有整數都小于 B 中的所有整數的要求。
def f(arr):
arr = sorted(arr)
pos = 0
sum_l, sum_r = 0, 0
while pos < (len(arr)-1):
sum_l, sum_r = sum(arr[:pos 1]), sum(arr[pos 1:])
pos = 1
if sum_l == sum_r:
return True
return False
我的想法是排序是O(nlogn)，while 回圈是O(n)，那么總體上arr[:pos 1]是 O(n) 并且總體arr[pos 1:]上也是 O(n)，所以總體上是O(nlogn) O(n*(n n)) = O(nlogn) O(n^2)。那是對的嗎？
另外，有沒有辦法擺脫這個切片運算子來降低復雜性？
uj5u.com熱心網友回復：
降低復雜度的一種簡單方法是避免在每次迭代時重復計算：
def foo(arr):
arr = sorted(arr)
sum_l = 0
sum_r = sum(arr)
for val in arr:
sum_l = val
sum_r -= val
if sum_l == sum_r:
return True
return False
但是，它的輸出對于第二個示例是不正確的。您可能需要調整演算法。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/477492.html