我有一组无序的 n
唯一的正整数。我想把它分成 ceil(n / k)
最多 k
的无序集合数字 ( k << n
) 以一种确定的方式(我想获得一系列相同的 ceil(n / k)
输出集而不依赖于输入的固定顺序)。
有没有一种方法可以做到这一点,其算法复杂度要优于对集合进行排序和对结果序列进行分区?
最佳答案
这是一种平均性能为 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)
中。
关于algorithm - 确定性地将集合划分为子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/69394625/