algorithm - 确定性地将集合分箱成子集

Question

我有一组无序的n唯一正整数。我想以一种确定的方式将它划分为最多为数字 ( ) 的ceil(n / k)无序集（我想获得相同输出集的序列，而不依赖于输入的固定顺序）。kk << nceil(n / k)

有没有一种方法可以在算法复杂性方面对集合进行排序和对结果序列进行分区？

标签： algorithmsettime-complexitycomplexity-theory

Answer 1

这是一种方法，其平均性能为O(n), 节拍O(n log(n))。

选择m，r < m < n其中r = ceil(n / k)是桶的数量。对于每个数字，将其散列并放入其中一个m袋子中。（我故意使用袋子和水桶，袋子更小。）这是一项O(n)任务。现在我们可以r通过遍历m袋子来构建我们的桶，当把桶装满时，我们可以快速选择一个m袋子。跑过那些包是，O(m)把它们放进去，然后用 quickselect 把包分割在一个边界上，这肯定是包含在里面的。rO(n)r-1O(r * (n/m))O(n)