1

我需要想出一个算法来执行以下操作：

假设您有一个正数数组（例如[1,3,7,0,0,9]），并且您事先知道它们的总和是 20。

你想从每个数字中提取一些平均数量，这样新的总和就会少 7。

为此，您必须遵循以下规则：

  • 你只能减去整数
  • 结果数组不能有任何负值
  • 您不能对存储桶的索引进行任何更改。

减法在数组上分布得越均匀越好。

这是我对 JavaScript + 下划线算法的尝试（可能会使其成为 n^2）：

function distributeSubtraction(array, goal){
    var sum = _.reduce(arr, function(x, y) { return x + y; }, 0);
    if(goal < sum){
      while(goal < sum && goal > 0){
         var less = ~~(goal / _.filter(arr, _.identity).length); //length of array without 0s
         arr = _.map(arr, function(val){ 
            if(less > 0){
                return (less < val) ? val - less : val; //not ideal, im skipping some! 
            } else {
                if(goal > 0){ //again not ideal. giving preference to start of array
                    if(val > 0) {
                        goal--;
                        return val - 1;
                    }
                } else {
                    return val;
                }
            }
         });
         if(goal > 0){
             var newSum = _.reduce(arr, function(x, y) { return x + y; }, 0);
             goal -= sum - newSum;
             sum = newSum;
         } else {
            return arr;
         }
      }
    } else if(goal == sum) {
      return _.map(arr, function(){ return 0; });
    } else {
      return arr;
    }
}
var goal = 7;
var arr = [1,3,7,0,0,9];
var newArray = distributeSubtraction(arr, goal);
//returned: [0, 1, 5, 0, 0, 7];

好吧，这行得通，但必须有更好的方法！我想这个东西的运行时间会随着更大的数组和更大的数字而变得很糟糕。

编辑：我想澄清这个问题纯粹是学术性的。把它想象成一个面试问题，你在白板上写一些东西，面试官会问你你的算法在不同类型的数据集上会如何表现。

4

2 回答 2

1

听起来您想从每个数字中减去加权数量。IE 你想X/sum * amount_to_subtract从每个项目中减去。您当然需要将减去的金额四舍五入。然后问题是确保您减去了正确的总金额。此外，这取决于您的输入：您是否保证可以减去您要减去的金额？这是一个粗略的python实现，（我认为）：

def uniform_array_reduction(inp, amount):
  total = sum(inp)
  if amount > total:
    raise RuntimeError('Can\'t remove more than there is')

  if amount == total: #special case
    return [0] * len(inp)

  removed = 0
  output = []
  for i in inp:
    if removed < amount:
      to_remove = int(round(float(i)/float(total)*float(amount)))
      output.append(i - to_remove)
      removed += to_remove
    else:
      output.append(i)
  # if we didn't remove enough, just remove 1 from
  # each element until we've hit our mark.
  # shouldn't require more than one pass
  while removed < amount:
    for i in range(len(output)):
      if output[i] > 0:
        output[i] -= 1
        removed += 1
        if removed == amount:
          break
  return output

编辑：我已经修复了代码中的一些错误。

于 2012-09-22T01:41:36.203 回答
1 
s = Sum(x) - required_sum
do:
    a = ceil( s/number_of_non_zeros(x) )
    For i=1 to length(x):
        v = min(a, x[i], s)
        x[i]-=v
        s-=v
while s>0

这个版本不需要排序。

于 2012-09-22T06:36:03.387 回答