一道數(shù)組算法題

每個數(shù)組元素值盡量相等

這個可以表述為 “使得標(biāo)準(zhǔn)差最小”，即

給出兩個數(shù) m, 及 n，求一個標(biāo)準(zhǔn)差最小的數(shù)組 array，并滿足 len(array) == m，且 sum(array) == n。

只要找出該數(shù)組，再隨機(jī)打亂元素順序便可。

我覺得很多同學(xué)都答出來了，本人傾向 @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)

當(dāng)然，他這里沒有做隨機(jī)操作。

既然你說盡量，那就盡量吧。

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))

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

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;
}

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;
}

這種方法也可以嘗試一下的

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)

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] 隨機(jī)
console.log(getArray(9, 4));   // [2, 2, 3, 2] 隨機(jī)順序
console.log(getArray(3, 4));  // [1, 0, 1, 1] 隨機(jī)順序

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

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;
}