algorithm - 发送批次面试算法

Question

我在另一个网站上遇到了以下面试问题：

您在收件箱中收到一堆电子邮件。您想将所有发件人地址发送到某个服务器。您可以分批发送它们（每批包含一堆发件人电子邮件地址）。限制是任何批次都不能包含重复的电子邮件地址。您将如何编写一个程序来分批发送所有电子邮件地址，从而使批次数量最少。

分析复杂性

我喜欢的答案是将电子邮件放入二叉搜索树（从而删除重复项），然后将其序列化并发送。这将只发送一批，并且是 O(n*log n) 时间。有人愿意提出更好的解决方案吗？

Answer 1

你可以使用hash，首先你检查特殊名称是否在hash中，如果没有，你将把它放在hash中并添加到batch中。这平均为 O(n)，但您当前的方法是 O(n logn)。

您当前的方法是 O(n log n)，因为创建二叉树需要 O(n logn)，因为您的任何比较基础算法都无法位n log n阻。

同样关于散列函数，它平均需要 O(n)。总而言之，它比排序方法在速度上要好，但它可能占用太多空间，你应该考虑你的数据格式。