将数组分成N组,使N组的和的差的绝对值最小

JavaScript018

将数组分成N组,使N组的和的差的绝对值最小,第1张

1 计算所有数的和

2 定义全局变量 保存最小值,初始化为所有数的和

3 递归执行加。

这步是关键,需要定义一个额外的数组,标记是否加过了,

每次递归的时候,找一个没加过的,累加上

然后用加出的和*2-所有数的和,找到该值绝对值最小的情况,就是要求的情况了。

PS:当递归得到的差值超过已有的最小值时,可以中断查找,减少查找次数。

原理:

如果所有和为sum 而选出数的和为sum1

那么 要求的结果是|sum1-(sum-sum1)| = |2*sum1-sum|

通过这样的转换,可以减少一点运算量。

求最大最小值,一般使用数学函数max和min。

具体用法:在es5中可以使用apply实现,即Math.min.apply(Math,arr);在es6中可以使用扩展运算符,即Math.min(...arr)。

这种方法只适合单值数组,如[1,2,3]。对于复杂数组和多维数组需要结合实际情况进行选择对应的方法。