我将字符串作为数组列表中的元素，我想使用 Java 在 O(logn) 时间内删除它们
我曾尝试使用HashSet复制和清除并复制回另一个数组列表，但我认为那是在 O(n) 时间内。
问问题
465 次
2 回答
3
我认为这是不可能的，即使你对数组进行了排序，它也需要O(n). 我认为你不能避免至少检查每个元素一次，所以复杂度不可能低于O(n).
于 2012-07-24T16:15:39.373 回答
0
如果数组中的字符串是按排序顺序排列的，则可以使用二进制搜索在 O(log n) 时间内访问它们；但是，如果它们未排序，则需要检查数组的每个元素，给出 O(n) 的下限。
编辑：如果您尝试从已创建的 ArrayList 中删除重复项，则必须查看每个元素，这将花费 O(n) 时间。如果您愿意牺牲添加，您可以将它们按排序顺序添加到数组中，然后您将永远不必删除重复项，因为如果一个元素已经存在，那么您就不要添加它；但是添加将在线性时间而不是恒定时间中运行。
于 2012-07-24T16:15:10.407 回答