查找出现在一组列表中的每一个中的所有数字

•浏览 1

Find all numbers that appear in each of a set of lists

我有几个整数对象的 ArrayLists，存储在 HashMap 中。

我想获取每个列表中出现的所有数字(整数对象)的列表(ArrayList)。

到目前为止我的想法是：

  • 遍历每个 ArrayList 并将所有值放入 HashSet
    • 这将为我们提供列表中所有值的"列表"，但只有一次
  • 遍历 HashSet

    2.1 每次迭代执行 ArrayList.contains()

    2.2 如果 ArrayLists 都没有为操作返回 false，则将该数字添加到包含所有最终值的"主列表"中。

    • 如果你能想出更快或更高效的方法，有趣的是，当我写这篇文章时，我想出了一个相当不错的解决方案。但我仍然会发布它以防万一它对其他人有用。

    当然，如果您有更好的方法，请告诉我。

    我不确定我是否理解您的目标。但是，如果您希望找到 List 对象集合的交集，则可以执行以下操作：

    public static List<Integer> intersection(Collection<List<Integer>> lists){

  if (lists.size()==0)

    return Collections.emptyList();



  Iterator<List<Integer>> it = lists.iterator();

  HashSet<Integer> resSet = new HashSet<Integer>(it.next());

  while (it.hasNext())

    resSet.retainAll(new HashSet<Integer>(it.next()));



  return new ArrayList<Integer>(resSet);

}

public class TestLists {



  private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();



  private static List<Integer> filter(List<List<Integer>> listOfLists) {



    // find the shortest list

    List<Integer> shortestList = null;

    for (List<Integer> list : listOfLists) {

      if (shortestList == null || list.size() < shortestList.size()) {

        shortestList = list;

      }

    }



    // create result list from the shortest list

    final List<Integer> result = new LinkedList<Integer>(shortestList);



    // remove elements not present in all list from the result list

    for (Integer valueToTest : shortestList) {

      for (List<Integer> list : listOfLists) {

        // no need to compare to itself

        if (shortestList == list) {

          continue;

        }



        // if one list doesn't contain value, remove from result and break loop

        if (!list.contains(valueToTest)) {

          result.remove(valueToTest);

          break;

        }

      }

    }



    return result;

  }





  public static void main(String[] args) {

    List<Integer> l1 = new ArrayList<Integer>(){{

      add(100);

      add(200);

    }};

    List<Integer> l2 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l3 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l4 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l5 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    listOfLists.add(l1);

    listOfLists.add(l2);

    listOfLists.add(l3);

    listOfLists.add(l4);

    listOfLists.add(l5);

    System.out.println(filter(listOfLists));



  }



}
Multiset<Integer> counter = HashMultiset.create();

int totalLists = 0;

// for each of your ArrayLists

{

counter.addAll(list);

totalLists++;

}



List<Integer> inAll = Lists.newArrayList();



for (Integer candidate : counter.elementSet())

 if (counter.count(candidate) == totalLists) inAll.add(candidate);`counter.addAll(list) => counter.addAll(Sets.newHashSet(list))

public List<Integer> intersection(Iterable<List<Integer>> lists) {



Iterator<List<Integer>> listsIter = lists.iterator();

if (!listsIter.hasNext()) return Collections.emptyList();

Set<Integer> bag = new HashSet<Integer>(listsIter.next());

while (listsIter.hasNext() && !bag.isEmpty()) { 

 Iterator<Integer> itemIter = listsIter.next().iterator();

 Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size

 Integer held;

 while (itemIter.hasNext() && !bag.isEmpty())

 if ( bag.remove(held = itemIter.next()) )

  holder.add(held);

 bag = holder;

}

return new ArrayList<Integer>(bag);

}

    此代码在项目总数中以线性时间运行。实际上这是平均线性时间，因为使用了 HashSet。

    另外，请注意，如果您在循环中使用 ArrayList.contains()，可能会导致二次复杂度，因为此方法在线性时间运行，而 HashSet.contains() 在恒定时间运行。

    您必须更改第 1 步：

    - 使用最短列表而不是您的 hashSet(如果它不在最短列表中，则它不在所有列表中......)

    然后在其他列表中调用 contains 并在一个返回 false 时删除值(并跳过对该值的进一步测试)

    最后，最短的列表将包含答案...

    一些代码：

    public static List<Integer> intersection(Collection<List<Integer>> lists){

  if (lists.size()==0)

    return Collections.emptyList();



  Iterator<List<Integer>> it = lists.iterator();

  HashSet<Integer> resSet = new HashSet<Integer>(it.next());

  while (it.hasNext())

    resSet.retainAll(new HashSet<Integer>(it.next()));



  return new ArrayList<Integer>(resSet);

}

public class TestLists {



  private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();



  private static List<Integer> filter(List<List<Integer>> listOfLists) {



    // find the shortest list

    List<Integer> shortestList = null;

    for (List<Integer> list : listOfLists) {

      if (shortestList == null || list.size() < shortestList.size()) {

        shortestList = list;

      }

    }



    // create result list from the shortest list

    final List<Integer> result = new LinkedList<Integer>(shortestList);



    // remove elements not present in all list from the result list

    for (Integer valueToTest : shortestList) {

      for (List<Integer> list : listOfLists) {

        // no need to compare to itself

        if (shortestList == list) {

          continue;

        }



        // if one list doesn't contain value, remove from result and break loop

        if (!list.contains(valueToTest)) {

          result.remove(valueToTest);

          break;

        }

      }

    }



    return result;

  }





  public static void main(String[] args) {

    List<Integer> l1 = new ArrayList<Integer>(){{

      add(100);

      add(200);

    }};

    List<Integer> l2 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l3 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l4 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l5 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    listOfLists.add(l1);

    listOfLists.add(l2);

    listOfLists.add(l3);

    listOfLists.add(l4);

    listOfLists.add(l5);

    System.out.println(filter(listOfLists));



  }



}
Multiset<Integer> counter = HashMultiset.create();

int totalLists = 0;

// for each of your ArrayLists

{

counter.addAll(list);

totalLists++;

}



List<Integer> inAll = Lists.newArrayList();



for (Integer candidate : counter.elementSet())

 if (counter.count(candidate) == totalLists) inAll.add(candidate);`counter.addAll(list) => counter.addAll(Sets.newHashSet(list))

public List<Integer> intersection(Iterable<List<Integer>> lists) {



Iterator<List<Integer>> listsIter = lists.iterator();

if (!listsIter.hasNext()) return Collections.emptyList();

Set<Integer> bag = new HashSet<Integer>(listsIter.next());

while (listsIter.hasNext() && !bag.isEmpty()) { 

 Iterator<Integer> itemIter = listsIter.next().iterator();

 Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size

 Integer held;

 while (itemIter.hasNext() && !bag.isEmpty())

 if ( bag.remove(held = itemIter.next()) )

  holder.add(held);

 bag = holder;

}

return new ArrayList<Integer>(bag);

}

    使用 Google Collections Multiset 使这(表示方式)变得轻而易举(尽管我也喜欢 Eyal 的回答)。它可能不如这里的其他一些在时间/内存方面有效，但很清楚发生了什么。

    假设列表本身不包含重复项：

    public static List<Integer> intersection(Collection<List<Integer>> lists){

  if (lists.size()==0)

    return Collections.emptyList();



  Iterator<List<Integer>> it = lists.iterator();

  HashSet<Integer> resSet = new HashSet<Integer>(it.next());

  while (it.hasNext())

    resSet.retainAll(new HashSet<Integer>(it.next()));



  return new ArrayList<Integer>(resSet);

}

public class TestLists {



  private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();



  private static List<Integer> filter(List<List<Integer>> listOfLists) {



    // find the shortest list

    List<Integer> shortestList = null;

    for (List<Integer> list : listOfLists) {

      if (shortestList == null || list.size() < shortestList.size()) {

        shortestList = list;

      }

    }



    // create result list from the shortest list

    final List<Integer> result = new LinkedList<Integer>(shortestList);



    // remove elements not present in all list from the result list

    for (Integer valueToTest : shortestList) {

      for (List<Integer> list : listOfLists) {

        // no need to compare to itself

        if (shortestList == list) {

          continue;

        }



        // if one list doesn't contain value, remove from result and break loop

        if (!list.contains(valueToTest)) {

          result.remove(valueToTest);

          break;

        }

      }

    }



    return result;

  }





  public static void main(String[] args) {

    List<Integer> l1 = new ArrayList<Integer>(){{

      add(100);

      add(200);

    }};

    List<Integer> l2 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l3 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l4 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l5 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    listOfLists.add(l1);

    listOfLists.add(l2);

    listOfLists.add(l3);

    listOfLists.add(l4);

    listOfLists.add(l5);

    System.out.println(filter(listOfLists));



  }



}
Multiset<Integer> counter = HashMultiset.create();

int totalLists = 0;

// for each of your ArrayLists

{

counter.addAll(list);

totalLists++;

}



List<Integer> inAll = Lists.newArrayList();



for (Integer candidate : counter.elementSet())

 if (counter.count(candidate) == totalLists) inAll.add(candidate);`counter.addAll(list) => counter.addAll(Sets.newHashSet(list))

public List<Integer> intersection(Iterable<List<Integer>> lists) {



Iterator<List<Integer>> listsIter = lists.iterator();

if (!listsIter.hasNext()) return Collections.emptyList();

Set<Integer> bag = new HashSet<Integer>(listsIter.next());

while (listsIter.hasNext() && !bag.isEmpty()) { 

 Iterator<Integer> itemIter = listsIter.next().iterator();

 Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size

 Integer held;

 while (itemIter.hasNext() && !bag.isEmpty())

 if ( bag.remove(held = itemIter.next()) )

  holder.add(held);

 bag = holder;

}

return new ArrayList<Integer>(bag);

}

    如果列表可能包含重复的元素，它们可以先通过一个集合：

    public static List<Integer> intersection(Collection<List<Integer>> lists){

  if (lists.size()==0)

    return Collections.emptyList();



  Iterator<List<Integer>> it = lists.iterator();

  HashSet<Integer> resSet = new HashSet<Integer>(it.next());

  while (it.hasNext())

    resSet.retainAll(new HashSet<Integer>(it.next()));



  return new ArrayList<Integer>(resSet);

}

public class TestLists {



  private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();



  private static List<Integer> filter(List<List<Integer>> listOfLists) {



    // find the shortest list

    List<Integer> shortestList = null;

    for (List<Integer> list : listOfLists) {

      if (shortestList == null || list.size() < shortestList.size()) {

        shortestList = list;

      }

    }



    // create result list from the shortest list

    final List<Integer> result = new LinkedList<Integer>(shortestList);



    // remove elements not present in all list from the result list

    for (Integer valueToTest : shortestList) {

      for (List<Integer> list : listOfLists) {

        // no need to compare to itself

        if (shortestList == list) {

          continue;

        }



        // if one list doesn't contain value, remove from result and break loop

        if (!list.contains(valueToTest)) {

          result.remove(valueToTest);

          break;

        }

      }

    }



    return result;

  }





  public static void main(String[] args) {

    List<Integer> l1 = new ArrayList<Integer>(){{

      add(100);

      add(200);

    }};

    List<Integer> l2 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l3 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l4 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l5 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    listOfLists.add(l1);

    listOfLists.add(l2);

    listOfLists.add(l3);

    listOfLists.add(l4);

    listOfLists.add(l5);

    System.out.println(filter(listOfLists));



  }



}
Multiset<Integer> counter = HashMultiset.create();

int totalLists = 0;

// for each of your ArrayLists

{

counter.addAll(list);

totalLists++;

}



List<Integer> inAll = Lists.newArrayList();



for (Integer candidate : counter.elementSet())

 if (counter.count(candidate) == totalLists) inAll.add(candidate);`counter.addAll(list) => counter.addAll(Sets.newHashSet(list))

public List<Integer> intersection(Iterable<List<Integer>> lists) {



Iterator<List<Integer>> listsIter = lists.iterator();

if (!listsIter.hasNext()) return Collections.emptyList();

Set<Integer> bag = new HashSet<Integer>(listsIter.next());

while (listsIter.hasNext() && !bag.isEmpty()) { 

 Iterator<Integer> itemIter = listsIter.next().iterator();

 Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size

 Integer held;

 while (itemIter.hasNext() && !bag.isEmpty())

 if ( bag.remove(held = itemIter.next()) )

  holder.add(held);

 bag = holder;

}

return new ArrayList<Integer>(bag);

}

    最后，如果您希望稍后可能需要一些额外的数据(例如，某个特定值与切入点有多接近)，这也是理想的选择。

    另一种稍微修改了 Eyal 的方法(基本上将通过集合过滤列表然后保留所有重叠元素的行为折叠在一起)，并且比上述更轻量级：

    public static List<Integer> intersection(Collection<List<Integer>> lists){

  if (lists.size()==0)

    return Collections.emptyList();



  Iterator<List<Integer>> it = lists.iterator();

  HashSet<Integer> resSet = new HashSet<Integer>(it.next());

  while (it.hasNext())

    resSet.retainAll(new HashSet<Integer>(it.next()));



  return new ArrayList<Integer>(resSet);

}

public class TestLists {



  private static List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();



  private static List<Integer> filter(List<List<Integer>> listOfLists) {



    // find the shortest list

    List<Integer> shortestList = null;

    for (List<Integer> list : listOfLists) {

      if (shortestList == null || list.size() < shortestList.size()) {

        shortestList = list;

      }

    }



    // create result list from the shortest list

    final List<Integer> result = new LinkedList<Integer>(shortestList);



    // remove elements not present in all list from the result list

    for (Integer valueToTest : shortestList) {

      for (List<Integer> list : listOfLists) {

        // no need to compare to itself

        if (shortestList == list) {

          continue;

        }



        // if one list doesn't contain value, remove from result and break loop

        if (!list.contains(valueToTest)) {

          result.remove(valueToTest);

          break;

        }

      }

    }



    return result;

  }





  public static void main(String[] args) {

    List<Integer> l1 = new ArrayList<Integer>(){{

      add(100);

      add(200);

    }};

    List<Integer> l2 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l3 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l4 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    List<Integer> l5 = new ArrayList<Integer>(){{

      add(100);

      add(200);

      add(300);

    }};

    listOfLists.add(l1);

    listOfLists.add(l2);

    listOfLists.add(l3);

    listOfLists.add(l4);

    listOfLists.add(l5);

    System.out.println(filter(listOfLists));



  }



}
Multiset<Integer> counter = HashMultiset.create();

int totalLists = 0;

// for each of your ArrayLists

{

counter.addAll(list);

totalLists++;

}



List<Integer> inAll = Lists.newArrayList();



for (Integer candidate : counter.elementSet())

 if (counter.count(candidate) == totalLists) inAll.add(candidate);`counter.addAll(list) => counter.addAll(Sets.newHashSet(list))

public List<Integer> intersection(Iterable<List<Integer>> lists) {



Iterator<List<Integer>> listsIter = lists.iterator();

if (!listsIter.hasNext()) return Collections.emptyList();

Set<Integer> bag = new HashSet<Integer>(listsIter.next());

while (listsIter.hasNext() && !bag.isEmpty()) { 

 Iterator<Integer> itemIter = listsIter.next().iterator();

 Set<Integer> holder = new HashSet<Integer>(); //perhaps also pre-size it to the bag size

 Integer held;

 while (itemIter.hasNext() && !bag.isEmpty())

 if ( bag.remove(held = itemIter.next()) )

  holder.add(held);

 bag = holder;

}

return new ArrayList<Integer>(bag);

}
  • 从第一个 List 创建一个 Set(例如 HashSet)。
  • 对于每个剩余的列表：
    • 如果 List 和 Set 都足够小，则调用 set.retainAll (list)
    • 否则调用 set.retainAll (new HashSet <Integer> (list))

    • 我不能说在哪个阈值之后步骤 2 的第二个变体变得更快，但我猜可能是 > 20 大小左右。如果你的列表都很小，你可以不用这个检查。

    我记得如果您不仅关心 O(*) 部分，而且关心因子，那么 Apache 集合具有更有效的纯整数结构。

赞 (0)
« 上一篇
下一篇 »

相关推荐

  • Spring部署设置openshift

    Springdeploymentsettingsopenshift我有一个问题让我抓狂了三天。我根据OpenShift帐户上的教程部署了spring-eap6-quickstart代码。我已配置调试选项，并且已将Eclipse工作区与OpehShift服务器同步-服务器上的一切工作正常，但在Eclipse中出现无法消除的错误。我有这个错误：cvc-complex-type.2.4.a:Invali…
    2025-04-161

  • 检查Java中正则表达式中模式的第n次出现

    CheckfornthoccurrenceofpatterninregularexpressioninJava本问题已经有最佳答案，请猛点这里访问。我想使用Java正则表达式检查输入字符串中特定模式的第n次出现。你能建议怎么做吗？这应该可以工作：MatchResultfindNthOccurance(intn,Patternp,CharSequencesrc){Matcherm=p.matcher…
    2025-04-161

  • 如何让 JTable 停留在已编辑的单元格上

    HowtohaveJTablestayingontheeditedcell如果有人编辑JTable的单元格内容并按Enter，则内容会被修改并且表格选择会移动到下一行。是否可以禁止JTable在单元格编辑后转到下一行？原因是我的程序使用ListSelectionListener在单元格选择上同步了其他一些小部件，并且我不想在编辑当前单元格后选择下一行。Enter的默认绑定是名为selectNext…
    2025-04-161

  • Weblogic 12c 部署

    Weblogic12cdeploy我正在尝试将我的应用程序从Tomcat迁移到Weblogic12.2.1.3.0。我能够毫无错误地部署应用程序，但我遇到了与持久性提供程序相关的运行时错误。这是堆栈跟踪：javax.validation.ValidationException:CalltoTraversableResolver.isReachable()threwanexceptionatorg.…
    2025-04-161

  • Resteasy Content-Type 默认值

    ResteasyContent-Typedefaults我正在使用Resteasy编写一个可以返回JSON和XML的应用程序，但可以选择默认为XML。这是我的方法：@GET@Path("/content")@Produces({MediaType.APPLICATION_XML,MediaType.APPLICATION_JSON})publicStringcontentListRequestXm…
    2025-04-161

  • 代码不会停止运行，在 Java 中

    thecodedoesn'tstoprunning,inJava我正在用Java解决项目Euler中的问题10，即"Thesumoftheprimesbelow10is2+3+5+7=17.Findthesumofalltheprimesbelowtwomillion."我的代码是packageprojecteuler_1;importjava.math.BigInteger;importjava…
    2025-04-161

  • Out of memory java heap space

    Outofmemoryjavaheapspace我正在尝试将大量文件从服务器发送到多个客户端。当我尝试发送大小为700mb的文件时，它显示了"OutOfMemoryjavaheapspace"错误。我正在使用Netbeans7.1.2版本。我还在属性中尝试了VMoption。但仍然发生同样的错误。我认为阅读整个文件存在一些问题。下面的代码最多可用于300mb。请给我一些建议。提前致谢publicc…
    2025-04-161

  • Log4j 记录到共享日志文件

    Log4jLoggingtoaSharedLogFile有没有办法将log4j日志记录事件写入也被其他应用程序写入的日志文件。其他应用程序可以是非Java应用程序。有什么缺点？锁定问题？格式化？Log4j有一个SocketAppender，它将向服务发送事件，您可以自己实现或使用与Log4j捆绑的简单实现。它还支持syslogd和Windows事件日志，这对于尝试将日志输出与来自非Java应用程序…
    2025-04-161
手机版技术脚本