3

我有一个 Java 集合<String username, ArrayList loginTimes>。例如，一个条目可能看起来像["smith", [2012-10-2 08:04:23, 2012-10-4 06:34:21]]. 时间有一秒的分辨率。我希望为在间隔超过 24 小时但间隔不到 7 天的时间内至少登录两次的所有用户输出用户名列表。

有一种简单的 O(n^2) 方法可以做到这一点，对于给定的用户，您将每个登录时间与其他每个登录时间进行比较，并检查它们是否符合所需条件。还有一些 O(nlogn) 的方法，比如将 loginTimes 存储为二叉搜索树，对于每个登录时间（N 个），通过树（log N）查看是否有另一个登录时间符合要求。

我的理解是，还有一个解决方案（O（n）或更好？），您可以从登录时间创建一个位数组（BitSet），并使用某种掩码来检查所需的条件（至少两次登录次相隔 24 小时，但相隔不到 7 天）。有人知道如何实现吗？还是其他可能的有效（O（n）或更好）解决方案？

4

1 回答 1

1

您可以在 O(M * NlogN) 中执行此操作，其中 M 是编号。用户数（集合的大小）和 N 的平均登录时间长度（它是一个数组）：


对于集合中的每个用户，请执行以下操作：
1- 对列表 loginTimes 进行排序。这是一个 O(NlogN) 任务
2- 扫描列表并搜索您的约束是否适用。这可以在 O(N) 时间内完成。

因此，对于每个用户，总成本为 O(N) + O(NlogN) => O(2N*logN) => O(NlogN)

于 2012-10-31T11:52:44.420 回答