将一个正整数组分成N组,使每组的数字之和相近.

  QQ群里有人发了个面试问题: `将一个正整数组分成3组,使每组的数字之和相近.` 闲得没事,写了个算法的[demo链接](http://lihuanghe.github.io/avalontest/#!/35). 其实这个题可以等同于: 将一个正整数组分成N组,使每组的数字之和等于平均数. 因为数组的总和是固定的,所以可以计算每组的和应该等于 Sum/N . 那么这道题就变成: `在一个数组内找出一组数,使其和等于M`. 

总体思想就是: 数组按从大到小排序,然后从第一个数开始,一个个试直到有一组数的sum符合要求.

详情看代码:

	function aaa(arr,sum){
		var oldsum = sum;
		var i=0; 		//用来记录当前正在处理的数字下标
		var ret = []; //保存返回结果的数组
		while(true){

			if(sum == 0) break; //sum为0表示找到了符合规则的数组子集了
			
			//因为已用过的数字要从数组删除掉,所以要跳过undefined 
			if(arr[i] === undefined && i<arr.length){
				i++;
				continue;
			}

			
			if(i == arr.length){
				//已是最后一个数了
				//从结果数组里弹出一个数, 用这此数的下一个数据进行测试
				var t = ret.pop();
				if(t){
					sum += arr[t];
					i = t+1;
					continue;
				}else{
					//结果集合内没有数字了,说明已尝试了所有数字
					break;
				}
						
			}

			if(sum > 0){
				//如果加上下一个数仍然小于sum,则把下一个数加入结果集,否则尝试更小的数
				if(sum - arr[i] >= 0){

					sum -= arr[i];
					ret.push(i++);
				
				}else{
				
					i++;
				}
			}
		}

		//所有可能都试过了.找到结果了就返回.
		if(sum == 0) {
			var result = [];
			var sum = 0;
			for(j in ret){
				result.push(arr[ret[j]]);
				sum += arr[ret[j]];
				delete arr[ret[j]] ;
			}
			return {"result":result,"sum":sum};
		}else{
		//还没找到结果,试试看有没有更接近的结果 : 即数组之和是sum-1的.
			if(oldsum - 1 > 0){
				return aaa(arr,oldsum-1);
			}else{
				return ;
			}
			
		}
	};

看下效果:

原始数组: 990 , 956 , 936 , 923 , 898 , 894 , 892 , 887 , 869 , 863 , 858 , 841 , 834 , 815 , 767 , 758 , 728 , 726 , 719 , 690 , 672 , 658 , 642 , 621 , 601 , 591 , 578 , 557 , 550 , 544 , 536 , 497 , 494 , 466 , 448 , 448 , 445 , 399 , 376 , 368 , 365 , 361 , 357 , 304 , 301 , 261 , 241 , 227 , 216 , 211 , 193 , 180 , 111 , 95 , 93 , 89 , 45 , 45 , 13 , 5=>31048

和平均数 (sum/3): 10349.333333333334
数组1: 990 , 956 , 936 , 923 , 898 , 894 , 892 , 887 , 869 , 863 , 858 , 241 , 93 , 45 , 5=>10350
数组2: 841 , 834 , 815 , 767 , 758 , 728 , 726 , 719 , 690 , 672 , 658 , 642 , 621 , 578 , 211 , 89=>10349
数组3: 601 , 591 , 557 , 550 , 544 , 536 , 497 , 494 , 466 , 448 , 448 , 445 , 399 , 376 , 368 , 365 , 361 , 357 , 304 , 301 , 261 , 227 , 216 , 193 , 180 , 111 , 95 , 45 , 13=>10349


各数据组之和的方差: 0.33333333333333337
blog comments powered by Disqus