一道看似非常难的面试算法题
这是昨天面试百度时碰到的一道算法题：任意数分三组，使得每组的和尽量相等（感谢博友提供的关于该问题的相关资料 划分问题）。由于时间仓促，加之面试时头昏脑涨，这道题没做出来甚至没有给出思路，这让我多少有些遗憾和不甘。因为最近接触算法的东西较多而且本身对算法感兴趣，所以回家之后绞尽脑汁想把这题做出来。其实刚看到这题时感觉不难，但是因为数字个数及数值的不确定，我感觉这题越想越难。昨天一晚上没有睡好，甚至做梦都在想这题！
今天上午在多个群里问了这题，都没有给出思路，真是绝望至极。很多人都说 n/3 的思路，其实这种思路一开始就是死胡同。本人属于那种不会轻言放弃之人，哈哈。本人多年经验得出一结论：只要认真思考，有耐心，很多问题都能迎刃而解。每次遇到难缠的问题，我都会抓耳挠腮，而一旦解决，又会手舞足蹈。跑远了，言归正传，中午正准备趴在工位上休息，眼睛扫了扫笔记本，瞬间茅塞顿开。真是踏破铁鞋无觅处，得来全不费工夫！果不其然，算法就是窗户纸！
我先说一下我的思路，首先一定要先排序，这也是解决问题的关键。然后降序排序后的前三个数各分一组（根据博友的评论，此处是问题所在，前三个数也有可能属于同一组，暂时没有想到好方法），把剩余数往三个数上叠加。我最开始的思路也是如此，问题在于分组个数不确定，出现极端大的数怎么办，怎么叠加？那层窗户纸就是将剩余数中的最大值加到前三个数的最小值上，然后重排序，继续叠加，直到数组个数剩三个为止！不知道这样说好不好理解，比如以下数组:
[3, 8, 20, 15, 60, 1, 32];
// 分组流程分解，根据博友评论，此方法属于贪心算法，只是局部求解：
// 1.从大到小排序
[60, 32, 20, 15, 8, 3, 1]
// 2.剩余数叠加
[60, 32, 35(20+15), 8, 3, 1]
// 3.重排序
[60, 35, 32, 8, 3, 1]
// 4.再叠加
[60, 35, 40(32+8), 3, 1]
// 5.重排序
[60, 40, 35, 3, 1]
// 6.再叠加
[60, 40, 38(35+3), 1]
// 7.结果
[60, 40, 39]我想看完上述流程演示，这个题基本就没问题了吧。上述流程最终输出的是每组的和，并没有反映出每组的分组情况。我们应该定义一个函数，输出带有分组情况的数组。比如：
var arr = [3, 8, 20, 15, 60, 1, 32];
function equal(arr) {
......
return array;
}
> input equal(arr)
< output [[60],[32,8],[20,15,8,3,1]]算法这东西，只有自己亲自思考出来才能深刻理解它。各位博友看到这里，可以自己试着写一下上面的函数，然后再对比我写的函数，如果你觉得你写的函数更优雅，欢迎给我留言！
以下是我写的算法，其实从有思路到写出程序也废了很大劲：
// 任意数分三组，每组和尽量相等（也就是最大值与最小值差值最小）
function equal(arr) {
var array = [];
arr = sortMArray(arr);
for (var i = 0; i < arr.length; i++) {
// 转换成多维数组
array.push([arr[i]]);
}
while (array.length > 3) {
array[2].push(array[3][0]);
array.splice(3, 1);
array = sortMArray(array);
}
return array;
}为了按要求输出数组，我还使用了多维数组排序及数组内元素求和的算法，我在此没有深究，只是普通的冒泡排序，如下：
// 计算数组元素和
function sum(o) {
var sum = 0;
if (Array.isArray(o)) {
o.map(function(item, index, array) {
sum += item;
});
} else {
sum += o;
}
return sum;
}
// 多维数组排序
function sortMArray(arr) {
for (var i = 0, len = arr.length; i < len - 1; i++) {
for (var j = i + 1; j < len; j++) {
if (sum(arr[i]) < sum(arr[j])) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
看着输出的结果，确实有点小激动~
最后，我们可以将此题再延伸一下，比如任意数分任意组，有了上面的算法，这个就很简单了，直接贴代码
// 计算数组元素和
function sum(o) {
var sum = 0;
if (Array.isArray(o)) {
o.map(function(item, index, array) {
sum += item;
});
} else {
sum += o;
}
return sum;
}
// 多维数组排序
function sortMArray(arr) {
for (var i = 0, len = arr.length; i < len - 1; i++) {
for (var j = i + 1; j < len; j++) {
if (sum(arr[i]) < sum(arr[j])) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
// 任意数分 n 组，每组和尽量相等（也就是最大值与最小值差值最小）
function equal(arr,n) {
var array = [];
arr = sortMArray(arr);
for (var i = 0; i < arr.length; i++) {
// 转换成多维数组
array.push([arr[i]]);
}
while (array.length > n) {
array[n-1].push(array[n][0]);
array.splice(n, 1);
array = sortMArray(array);
}
return array;
}
// 测试数组
var arr = [3, 8, 20, 15, 60, 1, 32];最后的最后还要说一句，也算是自我检讨以及对代码的孜孜以求，虽然功能完成了，但从程序员的角度来看，我还没有对输入参数进行校验，所以这样的代码还是有瑕疵的！