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

Question

我想通过创建一个新的 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。这是正确的吗？时间复杂度是多少？

Answer 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 - 如您所愿。