>假设我有一个正整数的向量 V。如果整数的总和大于正整数 N，我想重新缩放 V 中的整数，以便总和为 <= N。V 中的元素必须保持在零以上。V 的长度保证为 <= N。
有没有一种算法可以在线性时间内执行这种重新缩放？
顺便说一句，这不是家庭作业:)。我需要将地图从符号重新缩放到符号频率以使用范围编码。
一些快速的思考和谷歌搜索并没有给出解决问题的方法。
编辑：
好吧，这个问题有点不清楚。"重新缩放"的意思是"正常化"。也就是说，将 V 中的整数（例如通过将它们乘以常量）转换为较小的正整数，以便满足 sum（V） <= N 的标准。整数之间的比率保留得越好，压缩效果就越好。
这个问题是开放式的，该方法不需要找到保持比率的最佳（例如最小二乘拟合感）方法，而是"好"的方法。按照建议将整个向量设置为 1 是不可接受的（除非强制）。例如，"好"足以找到满足总和标准的最小除数（定义如下）。
以下朴素算法不起作用。
- 求当前总和（V），Sv
- 除数 ：= int（ceil（Sv/N））
- 将 V 中的每个整数除以除数，向下舍入，但不小于 1。
这在 v = [1,1,1,10] 且 N = 5 时失败。
divisor = ceil(13 / 5) = 3.
V := [1,1,1, max(1, floor(10/3)) = 3]
Sv is now 6 > 5.
在这种情况下，正确的归一化是 [1,1,1,2]
一种有效的算法是对除数（如上所述）进行二分搜索，直到找到 [1，N] 中满足 sum 准则的最小除数。从ceil（Sv/N）猜测开始。然而，这在操作数量上不是线性的，而是与len（V）*log（len（V）成正比的。
我开始认为，在一般情况下，在线性时间内不可能做得好。我可能会诉诸某种启发式方法。
只需将所有整数除以其最大公约数即可。您可以通过欧几里得算法的多种应用有效地找到 GCD。
d = 0
for x in xs:
d = gcd(d, x)
xs = [x/d for x in xs]
积极的一点是，您总是以这种方式尽可能小的表示形式，而不会丢弃任何精度，也不需要选择特定的 N。缺点是，如果你的频率是大的互质数，你别无选择，只能牺牲精度（而且你没有指定在这种情况下应该做什么）。
这个怎么样：
- 求当前总和（V），Sv
- 除数 ：= int（ceil（Sv/（N - |V|+ 1））
- 将 V 中的每个整数除以除数，向上舍入
在 v = [1,1,1,10] 且 N = 5 时：
除数 = ceil（13/2） = 7。V ：= [1,1,1， ceil（10/7）） = 2]
我认为您应该重新缩放 1 以上的部分。因此，从所有值中减去 1，从 N 中减去 V.length。然后正常重新缩放，然后向后添加 1。如果你继续运行总计，而不是只选择一个因素，你甚至可以做得更好一点，这通常会浪费一些"数字空间"。像这样：
public static void rescale(int[] data, int N) {
int sum = 0;
for (int d : data)
sum += d;
if (sum > N) {
int n = N - data.length;
sum -= data.length;
for (int a = 0; a < data.length; a++) {
int toScale = data[a] - 1;
int scaled = Math.round(toScale * (float) n / sum);
data[a] = scaled + 1;
n -= scaled;
sum -= toScale;
}
}
}
这是一个"范围规范化"的问题，但它很容易。假设 S 是向量元素的总和，S>=N，然后 S=dN，对于某个 d>=1。因此 d=信噪比。因此，只需将向量的每个元素乘以 N/S（即除以 d）。结果是一个具有重新缩放分量的向量，其总和正好为 N。这个过程显然是线性的:)