2012-09-22 97 views
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]; 

嗯,這工作,但必須有一個更好的辦法!我想象這個事情的運行時間會更長,陣列更大,數量更大。

編輯:我想澄清一下,這個問題純粹是學術問題。把它想象成一個面試問題,你在哪裏白板上做什麼,面試官問你如何在不同類型的數據集上表現你的算法。

+0

你的問題的實際維度是什麼?你的數組長度是多少?總和是多大?是應用大的區別/目標? (換句話說:定義「更好」並激發原因) –

+0

當我說得更好時,我的意思是更快的運行時和更優雅的代碼。在一個大數據集的情況下,我會關心運行時間而不是美容。如果數據集很小,則可以看到漂亮的代碼。 (我的問題的數據集很小,但通常這似乎是一個有趣的問題) – mkoryak

+0

好吧,好,更好意味着更快,是陣列的長度大嗎?你必須申請大的變化嗎?你預計哪一個會隨着問題的規模而變化? (如果我正在面試候選人,我會提供一些關於我感興趣的效率的指導,這就是爲什麼我會問。如果你在尋找N的效率,陣列的長度,這很酷,只是想知道) –

回答

1

這聽起來像是你想從每個數字中減去加權金額。 I.E你想從每個項目減去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 

編輯:我已經修復了代碼中的一些錯誤。

+0

我認爲這個算法可以在輸出數組中導致負數,這是我不允許有的一件事 – mkoryak

+0

我不認爲我很清楚這個規則:P編輯我的問題 – mkoryak

+0

它不應該有負數。它只能刪除總量的一小部分。我一直在運行的示例輸入似乎都有效。如果這真的是一個擔心,很容易說'to_remove = min(to_remove,i)' –

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 

該版本不需要排序。

+0

我想使用減法函數返回orinal數組。首先對它進行排序修改數組。對不起,應該包括這個作爲'規則' – mkoryak

+0

@mkoryak這個版本不需要排序。 – ElKamina

+0

什麼是new_cnz用於? – mkoryak

相關問題