将所有项目成对分为成对并获得其绝对差异,其绝对差异的最低总和是多少?
示例:
[4, 1, 2, 3] should return 2 because |1 - 2| + |3 - 4| = 2
[1, 3, 3, 4, 5] should return 1 because |3 - 3| + |4 - 5| = 1
确定具有均匀长度的数组的结果非常容易,因为它只需要对数组进行排序并获得彼此相邻的数字之间的差异。
,无论添加额外的数字,所以长度奇数的数组非常困难。因此,我当前的奇数阵列解决方案是删除每个数字并使用均匀的数组方法检查总和。
电流解决方案:
def smallest_sum(arr):
arr = sorted(arr)
if len(arr) % 2 == 0:
return even_arr_sum(arr)
else:
return odd_arr_sum(arr)
def even_arr_sum(arr):
total = 0
for i in range(0, len(arr), 2):
total += arr[i+1] - arr[i]
return total
def odd_arr_sum(arr):
total = 0
for i in range(len(arr)):
s = even_arr_sum(arr[:i] + arr[i+1:])
if total == 0 or s < total:
total = s
return total
assert smallest_sum([4, 1, 2, 3]) == 2
assert smallest_sum([1, 3, 3, 4, 5]) == 1
nove,这非常慢,并提供了N2的时间。是否有一种更聪明的方法来处理具有奇数长度的数组?
想象您已经将七个数字A分类为G,然后忽略A。您最终会添加或减去它们:
这通常是它的外观,因为省略了每个数字:
A B C D E F G
- + - + - + (leaving out A)
- + - + - + (leaving out B)
- + - + - + ...
- + - + - +
- + - + - +
- + - + - +
- + - + - +
从一排到另一行,几乎没有变化。因此,首先计算出抛弃A的总数。然后,对于抛弃B的总数,只需减去A并添加B。依此类推。