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

各数値から重み付けされた量を減算したいようです。X/sum * amount_to_subtract各アイテムから差し引くIE 。もちろん、減算する金額を丸める必要があります。問題は、正しい合計金額を差し引いたことを確認することです。また、これはあなたの入力に依存します:あなたが減算したい金額を減算できることを保証していますか? 大まかな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 に答える