假设我有n个不相交的整数间隔中的m个整数，它们在某种意义上是“相距较远”的。Ñ是不预先已知的，但是已知为小（见下面的假设）。
例如，对于n = 3，我可能已经从区间105-2400、58030-571290、1000000-1000100中获得了随机分布的整数。
找出最小值（105）和最大值（1000100）显然是微不足道的。
但是，是否有任何方法可以有效地（在O（m）时间，并希望在o（m）空间）找到间隔的边界点，以便我可以对数据进行快速分区以进行单独处理？
如果没有有效的方法来精确地做到这一点，是否有一种有效的方法可以将分区近似到一个小的常数因子（如2）之内？
（例如，4000是较小间隔的上限的可接受的近似值，而30000是中间间隔的下限的可接受的近似值。）
假设：
一切都是非负的
n非常小（例如<10）
最大值比较大（例如，约为2 26）
间隔是密集的（即，该间隔内的大多数值在数组中都有一个整数）
如果两个簇的最接近边界至少相距一个恒定因子c，则它们相距很远。
（编辑：是有意义的Ç是相对于所述簇的大小，而不是相对于结合的因此，在百万1个元件的簇应。不被近似为从区间500000-2000000始发。）
整数不排序，这很关键。实际上，没有基数排序就不可能在O（m）时间内对它们进行排序，但是基数排序可能具有O（max value）复杂性，并且不能保证最大值接近m的任何地方。
同样，速度是这里最重要的因素。只要误差在合理范围内，就可以容忍。
实际上，当我发布问题时，我认为我是错的-答案的确似乎是基数排序。
桶的数量是任意的，不必与间隔的大小相关。
如果我一点一点地去，甚至可能是2。
因此，基数排序可以帮助我按O（m log（max value））≈O（m）的时间对数据进行排序（因为根据假设，log（max value）本质上是26的常数），这时问题就解决了变得微不足道。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句