algorithm - 确定性地将集合划分为子集

Question

我有一组无序的 n唯一的正整数。我想把它分成 ceil(n / k)最多 k 的无序集合数字 ( k << n ) 以一种确定的方式(我想获得一系列相同的 ceil(n / k) 输出集而不依赖于输入的固定顺序)。

有没有一种方法可以做到这一点，其算法复杂度要优于对集合进行排序和对结果序列进行分区？

Answer 1

这是一种平均性能为 O(n) 的方法，优于 O(n log(n))。

用 m 选择 r < m < n ，其中 r = ceil(n / k) 是桶的数量。对于每个数字，对其进行哈希处理并将其放入 m 袋中的一个。 (我故意使用袋子和桶，袋子更小。)这是一个 O(n) 任务。现在我们可以通过遍历 r 包构建我们的 m 桶，当桶装满时，我们快速选择 m 包中的一个。遍历这些包是 O(m) ，将它们放入 r 是 O(n) ，用快速选择在边界上拆分 r-1 包是 O(r * (n/m)) ，它肯定包含在 O(n) 中。