正常化整數

Question

我有一個整數列表，我想規範化它們，使他們的總和是比方說100.因此，例如(1, 1, 1, 1) --> (25, 25, 25, 25)。這是比較容易實現的：

int sum = calcSum(list); 
double factor = 100.0/sum; 
List<Integer> newList = Lists.newArrayList(); 
for (Integer i : list) { 
    newList.add(i*factor); 
} 

這工作只要總和爲100除數很不幸，這映射(1, 2) --> (33, 66)，而不是(1, 2) --> (33, 67)。我可以添加四捨五入到我的解決方案

newList.add(i*factor); --> newList.add(Math.round(i*factor)); 

不幸的是，這仍然有問題，(1, 1, 1) --> (33, 33, 33)。我意識到在這種情況下，我需要添加某種tiebreaker，並隨意選擇其中一個條目爲34.假設比率爲(0.334, 0.333, 0.333)我想選擇第一個元素，而不是任意選擇。即使在一個完美的領帶的情況下，隨機選擇一個元素增加1是不夠好，因爲我可能不得不增加超過1.

我可能會想出一個不雅的算法，反覆選擇最大值（沒有選擇相同的元素兩次，並與任意tiebreaker），並增加它，直到總和爲100.有沒有更好的算法來做到這一點？

Answer 1

相反浮點除法，你可以使用一個整數帶餘除法。

private static int [] divide(int ... num) { 
    int [] ret = new int[num.length]; 
    int sum = sum(num); 
    int rem = 0; 
    for (int i = 0; i < ret.length; i++) { 
     int count = num[i]*100 + rem; 
     ret[i] = count/sum; 
     rem = count % sum; 
    } 
    return ret; 
} 

正如你所看到的，我們總是將剩下的部分帶到下一個迭代中並添加回去。通過總是在下一次迭代中補充餘數，我們總是知道何時需要添加「跳躍數」以達到100的精確總分。

這裏唯一的問題是額外的數字將被添加到最後一個元素，但我會讓你弄清楚如何改變它。 :)

這種追蹤您的錯誤並反饋回來的想法是一個強大的一般策略，用於許多算法中，最顯着的是在Bresenham line drawing algorithm。

Answer 2

根據您想達到什麼，你總是可以在最後一個整數設置爲丟失量：

int currentSum = 0; 
for (int i = 0; i < list.size - 2, i++) { 
    newList.add(list.get(i) * factor); 
    currentSum += list.get(i); 
} 
newList.add(sum - currentSum);