假设我有来自n个不相交整数区间的m个整数，它们在某种意义上是“遥远”的。
n事先不知道，但已知它很小（见下面的假设）。
例如，对于n=3，可能已经给了我从105-2400、58030-571290、1000000-1000100区间随机分布的整数。
找到最小值（105）和最大值（1000100）显然是微不足道的。
但是，有没有什么方法可以有效地（在o（m）时间内，并且希望在o（m）空间内）找到区间的边界点，以便我可以快速地将数据分割以进行单独处理呢？
如果没有有效的方法来做到这一点，有没有一种有效的方法来近似分区，在一个小的常数因子（如2）内？
（例如，4000是较小区间的上界的一个可接受的近似值，30000是中间区间下界的一个可接受的近似值。）
假设：
一切都是非负的
n很小（例如，最大值比较大（比如，大约226）
间隔是密集的（即在数组中存在一个整数，用于该区间内的大多数值）。
如果两个星团最近的边界相距至少是常数因子c，则它们相距很远。
（编辑：c相对于集群大小而不是绑定是有意义的因此，在1000000的1个元素的簇不应该被近似为源于间隔50000～200万。
整数没有排序，这一点很关键。事实上，在没有基数排序的情况下，在O（m）时间内排序它们是不可能的，但是基数排序可以具有O（max value）复杂度，并且不能保证最大值接近m。
再次强调，速度是最重要的因素；只要在合理的因素范围内，就可以容忍不准确。
最佳答案
我说移动到因子c的对数刻度来搜索间隔，因为你知道它们至少是c因子分开的。然后，制作一个计数器数组，每个计数器以(0.5X .. 0.5X+0.5)对数刻度对数字进行计数，其中X是所选计数器的索引。
比如，C是2，你知道最大上限226，所以你创建52个计数器，然后计算floor(2*log<sub>2</sub>i)哪里i是当前整数，并增加那个计数器。解析完所有m个整数后，遍历该数组，其中的每个0序列将意味着对应的对数间隔为空。
所以它的输出将是被占用的间隔序列，对数对齐到c的一半幂，也就是128，181，256，363，512等等。这满足了你对间隔边界精度的要求。
更新：您还可以存储达到间隔的最低和最高数量。一旦这样做，间隔的边界计算如下：
从计数器数组中的当前位置查找第一个非零计数器。取它的最低值作为下界。
在计数器数组中前进，直到在计数器中找到零或到达数组的末尾。取最后一个非零计数器的最大值。这将是当前间隔的上限。
继续，直到完全遍历数组。
返回找到的间隔集边界将是严格的。
例如：（抽象语言代码）
counters=[];
lowest=[];
highest=[];
for (i=0;i<m;i++) {
x=getNextInteger();
n=Math.floor(2.0*logByBase(c,x));
counters[n]++;
if (counters[n]==1) {
lowest[n]=x;
highest[n]=x;
} else {
if (lowest[n]>x) lowest[n]=x;
if (highest[n]<x) highest[n]=x;
}
}
zeroflag=true; /// are we in mode of finding a zero or a nonzero
intervals=[];
currentLow=0;
currentHigh=0;
for (i=0;i<counters.length;i++) {
if (zeroflag) {
// we search for nonzero
if (counters[i]>0) {
currentLow=lowest[i]; // there's a value
zeroflag=false;
} // else skip
} else {
if (counters[i]==0) {
currentHigh=highest[i-1]; // previous was nonzero, get its highest
intervals.push([currentLow,currentHigh]); // store interval
zeroflag=true;
}
}
if (!zeroflag) { // unfinished interval
currentHigh=highest[counters.length-1];
intervals.push([currentLow,currentHigh]); // store last interval
}