一道数组算法题

Question

给定 m = 9，n = 4
返回数组 arr=[2,3,2,2] 的长度为4，各元素和为9，每个数组元素值尽量相似（标准差最小）,且元素在数组中的位置尽量随机

function a(m,n){
 
}

a(9,4) // [2,3,2,2]

Answer 1

function foo(m,n){
  var i = parseInt(m/n)
  var j = m % n
  var arr = new Array(n).fill(i)
  arr[n-1] = arr[n-1]+j
  return arr
}

var d= foo(9,4)
console.log(d)

要尽理相似，哪么把取模的值平均分配一下就好了

function foo(m,n){
  var i = parseInt(m/n)
  var j = m % n
  console.log(j)
  var arr = new Array(n).fill(i)
  for(var d=0;d<j;d++){
    arr[d]=arr[d]+1
  }
  return arr
}

var d= foo(11,3)
console.log(d)

Answer 2

既然你说尽量，那就尽量吧。

function foo(sum, length) {
    let result = Array.from({ length }).fill(parseInt(sum / length));
    for (let i = 0; i < sum % length; i++) {
        result[parseInt(Math.random() * length)]++;
    }
    return result;
}

console.log(foo(9, 4))

而如果你要不尽量，那就这样吧。

function foo(sum, length) {
    let av = parseInt(sum / length);
    let result = Array.from({ length }).fill(av);

    function randomIndex(av) {
        let index = parseInt(Math.random() * length);
        return result[index] === av ? index : randomIndex(av);
    }

    for (let i = 0; i < sum % length; i++) {
        result[randomIndex(av)]++;
    }
    return result;
}

console.log(foo(134, 50))

Answer 3

function getArray(m, n) {
    let finalArr = [];
    if(m <= n) {
        for (let i = 0; i<n; i++) {
            if(i < m) {
                finalArr.push(1);
            } else {
                finalArr.push(0);
            }
        }
    } else {
        let element = Math.ceil(m/n);

        for (let j = 0; j < n; j++) {
            if(j < n - 1) {
                finalArr.push(element);
            } else {
                finalArr.push(m-element*(n-1));
            }
        }
    }

    return finalArr.sort(function(a, b){ 
        return  Math.random() - Math.random(); 
    });;
}

console.log(getArray(11, 3));  // [4, 3, 4] 随机
console.log(getArray(9, 4));   // [2, 2, 3, 2] 随机顺序
console.log(getArray(3, 4));  // [1, 0, 1, 1] 随机顺序

Answer 4

function run(m, n) {
  const d = {},
    v = parseInt(m / n),
    result = new Array(n).fill(v);
  let _v = m % n;
  while (!!_v) {
    const i = Math.floor(Math.random() * n);
    if (!d[i]) {
      result[i] += 1;
      d[i] = true;
      _v -= 1;
    }
  }
  return result;
}

Answer 5

每个数组元素值尽量相等

这个可以表述为 “使得标准差最小”，即

给出两个数 m, 及 n，求一个标准差最小的数组 array，并满足 len(array) == m，且 sum(array) == n。

只要找出该数组，再随机打乱元素顺序便可。

---

我觉得很多同学都答出来了，本人倾向 @papersnake 的一个答案

function foo(m,n){
  var i = parseInt(m/n)
  var j = m % n
  console.log(j)
  var arr = new Array(n).fill(i)
  for(var d=0;d<j;d++){
    arr[d]=arr[d]+1
  }
  return arr
}

var d= foo(11,3)
console.log(d)

当然，他这里没有做随机操作。

Answer 6

function fn(m, n) {
  let i = m % n;
  const result = new Array(n - i).fill(Math.floor(m/n));
  while(i > 0) {
    result.splice(Math.random()*result.length, 0, Math.ceil(m/n));
    i--;
  }
  return result;
}

这种方法也可以尝试一下的

Answer 7

function getArray(sum,length){
      var av = parseInt(sum / length);
      var left = sum % length;
      var leftIndex = Math.abs(left);
      var array = [];
     var step = left > 0 ? 1 : -1;
     for(var i = 0;i < length;i++){
           array.push(av);
     }
     for(var i = 0;i < leftIndex;){
           var pos = parseInt(Math.random() * length);
           var value = array[pos];
           if(value === av){
                    array[pos] = value + step;
                   i++;
             }
     }
    return array;
}
console.log(getArray(0,3));//0,0,0
console.log(getArray(-11,3));// -4,-4,-3
console.log(getArray(-11,4));//-3,-3,-2,-3
console.log(getArray(11,3));//4,4,3
console.log(getArray(16,4));//4,4,4,4

Answer 8

function exp(sum,len){
   let arr = new Array(len).fill(parseInt(sum/len))
   let arr2 = []
   for (let i=0;i<len;i++){
       arr2.push(i)
   }
   let len2 = sum%len

   for (let i=0;i<len2;i++){
        arr[arr2.splice(Math.floor(Math.random()*arr2.length),1)[0]]++
   }
  
   return arr;
}

Answer 9

a=(m,n)=>Array(n).fill(m/n|0).map((v,w)=>w<m%n?v+1:v)