gpt4 book ai didi

java - 删除 ArrayList 中重复项的时间复杂度

转载 作者:行者123 更新时间:2023-12-01 17:52:36 29 4
gpt4 key购买 nike

我想通过创建一个新的 ArrayList 来“删除”ArrayList 中的元素,该新的 ArrayList 包含除重复项之外的所有元素。重复项由比较器选择,并且应保持顺序。该算法只是迭代 ArrayList 并添加新列表中尚未存在的每个元素。这项工作是通过遍历整个 ArrayList 并检查是否相等的方法来完成的。这是代码:

public static <T> ArrayList<T> noDups(Comparator<T> cmp, ArrayList<T> l) {

ArrayList<T> noDups = new ArrayList<T>();
for(T o : l) {
if(!isIn(cmp, o, l))
noDups.add(o);
}
return noDups;
}

public static <T> boolean isIn(Comparator<T> cmp, T o, ArrayList<T> l) {
Iterator<T> i = l.iterator();
if (o==null) {
while (i.hasNext())
if (i.next()==null)
return true;
} else {
while (!(i.hasNext()))
if (o.equals(i.next()))
return true;
}
return false;
}

我很好奇这个算法的时间复杂度。我的想法是:第一步没有任何工作,因为 ArrayList noDups 是空的。第二步有一次检查,第三步为 3,依此类推到 n-1。所以我们有 1+2+...+n-1。这是正确的吗?时间复杂度是多少?

最佳答案

算法的时间复杂度为O(n^2),因为对于数组中的每个元素,您必须将其与每个元素进行比较之前添加了一个。您可以使用 Set 将其改进为 O(n*log(n)) 实际上 O(n) .

您提到您关心顺序,据您所知,HashSet 并不维护它。这是正确,但有一种方法可以让它发挥作用。像这样使用LinkedHashSet:

ArrayList<Integer> array = 
new ArrayList<>(Arrays.asList(1, 5, 4, 2, 2, 0, 1, 4, 2));
LinkedHashSet<Integer> set = new LinkedHashSet<>(array);

这将构造一个LinkedHashSet,其插入、删除和查找的时间复杂度为O(1)。重要的部分是此数据结构与典型的 HashSet 之间的区别。 LinkedHashSet 另外创建一个链表,指示元素的插入顺序。

如果您使用此循环运行上述代码:

for(Integer i : set) {
System.out.print(i + " ");
}

输出将是:1 5 4 2 0 - 如您所愿。

关于java - 删除 ArrayList 中重复项的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48329822/

29 4 0