将N个点放入n个区间的最佳算法是什么？

Question

假设我在区间0,1中有N个点，并且我已经把这个单位区间划分为n个子区间，例如[0，x1)，[x1，x2)，…，[xn-2，xn-1)，xn-1,1，那么我需要确定每个N点属于哪个子区间。完成这项工作的最佳算法是什么？这些子区间不均匀分布，但它们是已知的。N是O(100万)，n是O(1k)。

Answer 1

如果点未排序，则按坐标对其排序。

对带间隔列表的点列表执行合并(如MergeSort中的合并算法)。

复杂性为O(NlogN + N + n) (如果已经对两个列表进行排序，则为O(N + n) )

与@Mukul接近复杂性O(Nlogn)进行比较，并为您的情况选择最佳变体

Answer 2

假设每个区间的下界，即0，x1，x2，x3.按顺序排列，保留数组中间隔的第一个值(即下界)，然后使用二进制搜索来定位大于或小于n所属的索引。