在号码列表中生成号码范围

最简单的方法是对数组进行排序，然后执行单个顺序传递以捕获范围。这对于您的目的来说可能已经足够快了。

我想到了两种技术:直方图和排序。直方图对于密集的数字集(大多数数字在min和max之间)是很好的，如果你有稀疏的数字集(实际上很少使用min和max之间的数字)排序是很好的。

对于直方图，只需遍历数组并在相应位置直方图中设置布尔标志为True，然后遍历直方图查找True的运行(默认应为false)。

对于排序，只需使用最佳适用的排序技术对数组进行排序，然后遍历排序后的数组，寻找连续的运行。

编辑:一些例子。

假设您有一个包含前1,000,000个正整数的数组，但是191的所有偶数倍数都被删除(您事先不知道这一点)。直方图将是一个更好的方法。

假设你有一个数组，包含2(2,4,8,16，…)和3(3,9,27,81，…)的幂。对于大列表，列表将是相当稀疏的，排序应该做得更好。

如Mike所说，首先对列表进行排序。现在，从第一个元素开始，记住这个元素，然后把它和下一个元素比较。如果下一个元素比当前元素大1，你就有一个连续的序列。继续这样做，直到下一个数字不是连续的。当您到达该点时，您将拥有从第一个记住的值到当前值的范围。记住/输出该范围，然后重新开始，将下一个值作为新系列的第一个元素。这将在大约2N时间内执行(线性)。

我会对它们进行排序，然后检查是否有连续的数字。如果差值大于1，则有一个新的范围。