java - 有效比较两个 ArrayList 的内容

Question

知道为什么contains在这里不起作用，这些语句总是评估falsefirstSchema.contains(firstSchema.get(0))

    List<String> firstSchema = new ArrayList<String>();
    firstSchema.add(0,"test");
    firstSchema.add(1,"testy");

    if(!(firstSchema.contains(firstSchema))){
        System.out.println("hey arraylist content matched");
    }

如果一个数组列表中的任何一个或多个或所有元素与其他数组列表元素匹配，我需要得到 true

Answer 1

检查一个列表是否包含另一个列表中的任何元素的最简单方法是调用 contains()在其中一个列表上，依次传递每个元素作为参数。像这样的东西:

public <E> boolean slowListContains(List<E> a, List<E> b) {
  for (E element : a) {
    if (b.contains(element)) {
      return true;
    }
  }
  return false;
}

但是，这很慢，因为 contains() 是一个线性运算 (O(n))，而且由于我们在循环中调用它，slowListContains() 函数需要二次时间 (O(n^2))，这很差。我们可以做得更好。

一个Set (或更准确地说，基于散列的集合，例如 HashSet )具有高效的 contains() 方法，该方法在低于线性的时间内运行(在 HashSet< 的情况下为恒定时间)/)。将一个或另一个列表转换为 Set 将使 slowListContains() 中的循环更快。像这样的东西:

public <E> boolean fasterListContains(List<E> a, List<E> b) {
  Set<E> aSet = new HashSet<>();
  aSet.addAll(a);
  for (E element : b) {
    if (aSet.contains(b)) {
      return true;
    }
  }
  return false;
}

这并不完美，但它肯定比简单的解决方案快得多。一个小小的改进是始终将较小的列表转换为 Set，而不是第一个列表。您还可以采用任意 Iterable 参数而不是 List 参数，然后检查它们中的任何一个是否已经是 Set ，如果是，则跳过 set-施工步骤。