数组中数字的均匀分布

Question

我的问题是我有一个给定的数组，其中包含 1 到 100 之间的 n 个数字。目标是选择 5 个数字，使总距离最小。总距离是通过将初始数组中的每个数字与最接近的 5 个选择数字的距离相加来计算的。

我（有点）尝试和思考的事情：

取数组的平均数除以5得到有用的东西？
将数组长度除以5，得到x，然后第一个数是array[x]，第二个是array[x*2]，依此类推

例子

输入 [5, 10, 15, 20, ..., 85, 90, 95, 100]
输出 [10, 30, 50, 70, 90] （可能会有更好的输出，但我希望这能使目标明确）

如您所见，我很迷茫，想不出解决办法。可能有一个超级简单的解决方案，我就是不明白。

我只是在寻找提示而不是解决方案，我不想自己弄清楚。

Answer 1

这是一个在多项式时间内工作的算法。

首先，对您的 n 数组进行排序。接下来，计算一个二维数组，其中每个 0 <= i <= j < n 包含最佳元素的索引，以填充从第 i 个元素到第 j 个元素的范围。从该最佳数组中为每个间隔填写一个类似的总距离数组。

作为上述示例输出的示例，第一个二维数组可能如下所示：

optimal_index = [
    [ 0,  0,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9],
    [ 1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10],
    [ 2,  2,  3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10],
    [ 3,  3,  4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11],
    [ 4,  4,  5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11, 11],
    [ 5,  5,  6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11, 11, 12],
    [ 6,  6,  7,  7,  8,  8,  9,  9, 10, 10, 11, 11, 12, 12],
    [ 7,  7,  8,  8,  9,  9, 10, 10, 11, 11, 12, 12, 13],
    [ 8,  8,  9,  9, 10, 10, 11, 11, 12, 12, 13, 13],
    [ 9,  9, 10, 10, 11, 11, 12, 12, 13, 13, 14],
    [10, 10, 11, 11, 12, 12, 13, 13, 14, 14],
    [11, 11, 12, 12, 13, 13, 14, 14, 15],
    [12, 12, 13, 13, 14, 14, 15, 15],
    [13, 13, 14, 14, 15, 15, 16],
    [14, 14, 15, 15, 16, 16],
    [15, 15, 16, 16, 17],
    [16, 16, 17, 17],
    [17, 17, 18],
    [18, 18],
    [19],
]

其中 i 到 j 范围内的最佳元素的索引在 optimal_index[i][j-i]。使用相同的索引方案，成本矩阵将是：

optimal_cost = [
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360, 405, 450, 500],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360, 405, 450],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360, 405],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320, 360],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280, 320],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245, 280],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210, 245],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180, 210],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150, 180],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125, 150],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100, 125],
    [ 0, 5, 10, 20, 30, 45, 60, 80, 100],
    [ 0, 5, 10, 20, 30, 45, 60, 80],
    [ 0, 5, 10, 20, 30, 45, 60],
    [ 0, 5, 10, 20, 30, 45],
    [ 0, 5, 10, 20, 30],
    [ 0, 5, 10, 20],
    [ 0, 5, 10],
    [ 0, 5],
    [ 0],
]

现在如果我们用 2 个元素填充范围呢？这是一个获取每个范围的问题，并查看我们可以划分的每个点的成本。这个新的数据结构只需要包含 "closest to first element" 和 "closest to second" 之间的分隔符。从这个除法中我们可以取任何范围并快速将其划分为最佳的 2，然后告诉你这两个选择的元素是什么，以及总成本。这可以用类似的矩阵填充。请注意，前面的 optimal_cost 矩阵将使这些计算非常简单。

接下来，包含 4 个元素的范围呢？这与我们现在在第一对和第二对之间划分的 2 个元素的范围除了完全相同。但是道理是一样的。

最后，我们的 5 个元素的问题呢？这只是计算最接近前 4 个元素和最接近最后一个元素之间的最佳划分的问题。因此，请尝试所有可能性。

在大小为 n 的数组中填充 k 事物的自然概括是 O(n^3 log(k))。

数组中数字的均匀分布

Even distribution of numbers in array

language-agnostic

algorithm