我需要拿出一個算法,執行以下操作:想出一個好的算法的一個簡單的想法
比方說你有正數的陣列(例如[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];
嗯,這工作,但必須有一個更好的辦法!我想象這個事情的運行時間會更長,陣列更大,數量更大。
編輯:我想澄清一下,這個問題純粹是學術問題。把它想象成一個面試問題,你在哪裏白板上做什麼,面試官問你如何在不同類型的數據集上表現你的算法。
你的問題的實際維度是什麼?你的數組長度是多少?總和是多大?是應用大的區別/目標? (換句話說:定義「更好」並激發原因) –
當我說得更好時,我的意思是更快的運行時和更優雅的代碼。在一個大數據集的情況下,我會關心運行時間而不是美容。如果數據集很小,則可以看到漂亮的代碼。 (我的問題的數據集很小,但通常這似乎是一個有趣的問題) – mkoryak
好吧,好,更好意味着更快,是陣列的長度大嗎?你必須申請大的變化嗎?你預計哪一個會隨着問題的規模而變化? (如果我正在面試候選人,我會提供一些關於我感興趣的效率的指導,這就是爲什麼我會問。如果你在尋找N的效率,陣列的長度,這很酷,只是想知道) –