JavaScript 分组

[mqliutie]

蚂蚁的笔试题

给定整数 n 和 m，写一个函数 dispatch ，把 1-n 尽量平均地分成m个组
如

var n = 2, m = 2;

dispatch(n, m) 得到[[1], [2]];

我自己实现的太烂了，所以想看看大家有没有什么好的实现方式

[ke1vin4real]

怎么算尽量平均 @mqliutie

[mqliutie]

@longxingren 例子不就能看出来嘛...
m个组中,最多的组内,元素数量也就比最少的多1

[mqliutie]

多给几个例子就是这样的

dispatch(5, 2) // [ [ 1, 2, 3 ], [ 4, 5 ] ]
dispatch(10, 6) //[ [ 1, 2 ], [ 3, 4 ], [ 5, 6 ], [ 7, 8 ], [ 9 ], [ 10 ] ]

[wangyue57]

function dispatch(n, m) {
    let base = Math.floor(n / m)
    let extra = n - m * base

    return [...Array(m)].map((v, i) => {
        let hasExtra = i < extra
        let jMax = base + (hasExtra ? 1 : 0)
        let baseNum = i * base + 1 + (hasExtra ? i : extra)

        return [...Array(jMax)].map((v, j) => j + baseNum)
    })
}

[ningt]

假如对分开后每个组的数字没有顺序要求的话

function dispatch(n, m) {
	var i, j, arrays = [];

	for (i = 0; i < m; i++)
		arrays.push([]);

	for (i = 1, j = 0; i <= n; i++, j = (j+1) % m)
		arrays[j].push(i);

	return arrays;	
}

-----------------------------------------------
dispatch(5, 2)  // [[1,3,5],[2,4]]
dispatch(10, 6) // [[1,7],[2,8],[3,9],[4,10],[5],[6]]

[mqliutie]

@Wang-NQXB 我记得 Array(number) 这种方式在不同浏览器构造出来的数组是不同的,兼容性可能会出现问题

[wangyue57]

@mqliutie 做这种面试题还要考虑兼容性么。。。 那就用for好了。 不考虑数字顺序的话，@ningt 提供了更好的方法。

[baofengs]

感觉这个答案比较啰嗦，有什么可优化的，欢迎指出，谢谢

思路：

• 问题转化为将 n 个小球放到 m 个框子里边
• 计算每个框子至少可以放多少个小球: Math.floor(n/m)，注意取整
• 计算剩下多少个小球：left = n % m，剩下的小球放到前 left 个框子里边
• 将相关数据填充到框子里边即可

function dispatch (n, m) {
    // 每个框子至少可以放几个球
    var least = Math.floor(n / m);
    // 剩下多少个球
    var left = n % m;
    // 框子
    var buckets = [];
    var last = 1;
    for (var i = 0; i < m; i++) {
        let bucket;
        if (left-- > 0) {
            bucket = generateArray(last, least + 1);
        } else {
            bucket = generateArray(last, least);
        }
        buckets.push(bucket);
        last = getMaxOfArray(buckets[i]) + 1;
    }
    // console.log(buckets, least, left);
    return buckets;
}

/**
 * 生成数组
 * 感觉有更 hack 的方法
 * @param base {number} 基址
 * @param offset {number} 偏移量
 * @return Array
 * eg: generateArray(3, 2) => [3, 4]
 */
function generateArray(base, offset) {
    var end = base + offset;
    var target = [];
    for (base; base < end; base++) {
        target.push(base);
    }
    return target;
}

/**
 * 获取数组中的最大值
 */
function getMaxOfArray(arr) {
    return Math.max.apply(null, arr);
}

// dispatch(10, 6);
// dispatch(4, 5);
dispatch(5, 4);

[Stevenzwzhai]

这个可以按照顺序分割

function dispatch(n, m){
    let restNums = n%m;
    let intervalIndex = Math.floor(n/m)
    let result = []
    let allArr = new Array(n).fill(1).map((i, index) => index);
    console.log(restNums, intervalIndex, allArr)
    for(let i=0; i < (m-restNums)*intervalIndex; i+=intervalIndex){
        console.log(i)
        result.push(allArr.slice(i, i+intervalIndex));
    }
    for(let j = (m-restNums)*intervalIndex; j < n; j+=(intervalIndex+1)){
        
        result.push(allArr.slice(j, j+intervalIndex+1))
    }

    return result
}

console.log(dispatch(20, 7))

[insist-git]

按自己的思路写个顺序分割，仅供参考可能还有更好的思路。
思路：先算每个分隔的数组长度，然后在按照顺序放数字即可。

 function dispatch(n, m) {
	    var  as, i, j, c= 1, arrs = [];
	     as = Math.floor(n/m); //取整
	     for (i = 0; i < m; i++){
		    arrs.push([]); //初始化分隔的数组
		    for ( j = 0; j < (i < n % m ? as+1 : as); j++) //分隔的数组长度
		    arrs[i].push(c++);   //按照顺序放数字  
	     }
	     return arrs;
}
 console.log(dispatch(20, 6)) ;

//  [[1, 2, 3, 4],[5, 6, 7, 8], [9, 10, 11], [12, 13, 14], [15, 16, 17], [18, 19, 20]]

(6) [Array(4), Array(4), Array(3), Array(3), Array(3), Array(3)]

[evilrescuer]

function dispatch(max, groupCount) {
    const res = []
    res.length = groupCount
    for(let i=0; i<res.length; i++) res[i] = []
    
    for(let i=1; i<=max; i++) {
        let index = i % groupCount - 1
        if(index === -1) index = groupCount - 1
        res[index].push(i)
    }
    return res
}

[JianJroh]

// 场景化为手持n张牌轮流派给m个人
function dispatch(n, m) {
    const arrays = Array(m).fill('').map(() => []);
    for (let i = 1; i <= n; i++) {
	const flag = (i-1) % m;
	arrays[flag].push(i);
    }
    return arrays;
};
dispatch(10, 6);
dispatch(5, 2);

[coolseaman]

const dispatch = (n, m) => {
    const res = [];
    for (let i = 0; i <= n; i++) {
        let index = i % m;
        res[index] = res[index] !== undefined ? [...res[index], i + 1] : [i + 1];        
    }

    return res;
}