javascript - 非负集减法

Question

这适用于任何语言，但我会在节点中实现它。

我有一组整数，以及一个我需要从该组总和中减去的值。

[4, 5, 6, 7, 8] - 25

如果我们从每个数字中均匀减去，我们会得到:

[-1, 0, 1, 2, 3]

但是，我不想要任何小于 0 的数字。因此，如果我正在编写一个算法来执行此操作，负数将平均溢出到其余数字中，我们现在有:

[0, 0, 1, 2, 3] - 1

制作结果集:

[0, 0, 1 - 0.333, 2 - 0.333, 3 - 0.333]

有没有不循环直到完成的快速操作或系列操作来解决这个问题？

请注意，这正是我想要的结果。所有负值均匀地溢出到剩余的正值中。

我使用 Lodash，所以 Lodash 中的答案是可以接受的。

Answer 1

你可以减少很多需要的循环，假设数字集

1. 只有正值
2. 集合的总和大于要减去的值
3. 可以排序。

关于第 3 点。您在评论中说可以对此进行排序，所以这是我想到的算法。它在变量名方面很冗长，但希望它能使它更清楚。总而言之，它并不太复杂:

const result = subtractFromSet([4, 5, 6, 7, 8], 25);
console.log(result)

function subtractFromSet(numberSet, totalToSubtract) {
  return numberSet.map((currentMember, index, wholeSet) => {
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    return currentMember - toSubtract;
  })
}

用文字来解释，这是正在发生的事情

1. 从集合的总和中减去一个值等同于从每个成员中减去除以集合大小的值。所以 [4, 5, 6, 7, 8] - 25 会是 4 - 5, 5 - 5, 6 - 5等
2. 如果我们不想要负数，那么我们只减去 最多 当前成员。因此，对于当前成员 4 和平均值为 25/5 = 5，我们只能减去 4。
3. 为了分散剩余部分，我们只需将其加回到剩余的总数中，以便为其余成员减去。所以当我们得到第二个成员 5 时，平均值现在是 (25 - 4)/(5 - 1) 因为我们不能减去完整的 5第一次求平均，只有4，其余元素少一个。这会产生 5.25。

因此，当遍历每个成员并调整总数然后减去平均值时，我们得到了正确的结果。虽然，请注意 floating point arithmetic在编程中，因为它可能导致结果略有偏差。如果您四舍五入到足够多的有效数字来满足您的需求，则可以在很大程度上避免这种情况。

最后一件事 - 正如我所说，必须对输入进行排序。这可以像这样轻松完成:

const unsortedArray = [6, 4, 7, 8, 5];
const sortedArray = unsortedArray.sort((a, b) => a - b)

console.log(sortedArray);

我将其从上述算法中删除，以专注于我们对排序后的输入实际执行的操作。

这个算法的总复杂度相当不错 - 一个不错的排序将为您净 O(n log(n)) 时间复杂度。取决于排序实现和数据集 - 5 个元素可能通过 O(n^2) Bubblesort 进行排序，但话又说回来，它是 5 个元素，因此它可能不会产生影响。运行减法算法是一个简单的 O(n)。减法的空间复杂度为 O(2n)，因为 .map() 复制了数组。我选择它是因为它更干净一些，因为您仍然有输入。但您也可以在原地进行减法，只需进行最小的更改，这将为您带来 O(n) 空间复杂度。

const input = [4, 5, 6, 7, 8];
subtractFromSet(input, 25);
console.log(input);

function subtractFromSet(numberSet, totalToSubtract) {
  numberSet.forEach((currentMember, index, wholeSet) => { //using .forEach instead of .map
    const remainingElements = wholeSet.length - index
    const averageToSubtract = totalToSubtract / remainingElements;
    
    const toSubtract = Math.min(averageToSubtract, currentMember);
    //modify both the total remaining to subtract and the current element
    totalToSubtract -= toSubtract;
    wholeSet[index] = currentMember - toSubtract; //modify the array directly
  })
}