algorithm - 发送批量采访算法

Question

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

You are given a bunch of emails in an inbox. You want to send all the sender addresses to some server. You can send them in batches (each batch containing a bunch of sender email addresses). The restriction is that no batch can contain duplicate email address. How would you write a program to send all the email addresses in batches such that it takes the minimum number of batches.

Analyze the complexity

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

Answer 1

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

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

还有关于哈希函数，它平均需要 O(n)。总的来说速度上比排序方法好，但是占用的空间可能太大，你应该考虑你的数据格式。