DSA 图：如何以编程方式将 n 个点划分为 N 个组，以便直观地在每个组内点“靠近”在一起？

Question

正如标题所示，我需要帮助开发一种算法，根据项目的接近程度，有效地将多个（n）个点一起划分为多个（N）个组。最后，我想显示以尽可能最小的误差形成的组。

问题点

更准确地说，每个点都是 x 轴上的一个数字，分区“好”程度的衡量标准可以定义为以下公式：所有点的总和除以总点数。

我尝试创建一个函数来计算给定点之间的误差，我可以做得很好，但我在显示组时遇到一些困难。

Answer 1

如果所有点都在 x 轴上，那么有 1 种方法，看起来相对明显且快速。 计算相邻点之间的差异（可能需要排序才能获得此序列），然后沿着 k 个最大差异进行分区以获得 k + 1 个簇。复杂度为 nlog(n)，它将在 x 轴上使用最小空间来优化集群。