我有一个 User 类
,它有 3 个对象(?)我不确定术语。
- (整数)ID 代码
- 用户创建的(整数)日期
- 和(字符串)名称
我正在尝试创建一种方法
- 将用户添加到我的数据结构 (1)
- 根据 ID 号返回用户的姓名 (2)
- 返回按日期排序的所有用户的完整列表 (3)
- 返回姓名包含特定字符串的用户列表,按日期排序 (4)
- 返回在特定日期 (5) 之前加入的用户列表
我根据加入年份(2004-2014)创建了 10 个数组,然后再次按日期对数组中的元素进行排序(按月然后日排序)
我是否正确地认为这意味着方法 (3) 和 (5) 具有 O(1)
时间复杂度,但 (1)、(4) 和 (2) 具有 O(N)
?
还有另一种数据结构/方法可以用来为我的所有方法提供 O(1)
吗?我反复尝试想出一种方法,但方法 (2) 的包含却让我难住了。
最佳答案
基于比较的排序始终为 O(N*log N),并且添加到已排序的容器为 O(log N)。为了避免这种情况,你需要水桶,就像你多年来一直拥有的那样。这会用内存换取执行时间。
仅当您仅将内容添加到 HashMap
时,(1) 才可以是 O(1)。
如果您有一个单独的 HashMap
将 ID 映射到用户,(2) 的复杂度可以是 O(1)。
(3) 当然是 O(N),因为你需要列出所有 N 个用户,但是如果你有一个 HashMap
,其中 key 是日期,value 是用户列表,那么你只需要通过恒定(10年* 365天+ 2)数量的数组来列出所有用户。所以 O(N),其中 (1) 仍然是 O(1)。假设用户在一天之内未排序。
(4) 与 3 基本相同,实现简单,只是打印较少。您也许可以使用 trie 或其他东西来加速最佳情况,但它仍然是 O(N),因为它将匹配 N 的某些百分比。
(5) 与(3)相同,只是可以更快爆发。
关于java - 使这个HashMap更高效的方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22000639/