algorithm - 规范化整数

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) 的问题。我意识到在这种情况下我需要添加某种决胜局并任意选择其中一个条目为 34。假设比率是 (0.334, 0.333, 0.333) 我想选择第一个元素，而不是随意选择。即使在完美平局的情况下，随机选择一个元素递增 1 也不够好，因为我可能不得不递增超过 1。

我可能想出一个不优雅的算法，它重复选择最大值(没有两次选择相同的元素并使用任意的决胜局)并递增它直到总和为 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 .