草庐IT

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

codeneng 2023-03-28 原文

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，则将该数字添加到包含所有最终值的"主列表"中。

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

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

    • 您的第一个解决方案将在 O(n) 时间内完成，无需额外的存储空间，我非常怀疑您能否击败它。
    • 感谢您为我的直觉增添了一些严谨性；)
    • 如果您的两个列表是 [1, 1, 2] 和 [1, 1, 3]，您希望输出是 [1, 1] 还是只是 [1]？即您是否希望保留重复项？
    • 只是 1 - 我不需要重复 - 为反应缓慢而道歉，昨天正在打高尔夫球(当你们为我做我的工作时，我感觉很糟糕)

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    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);
    }

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

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

    • 可能值得在你的 while 循环中对 resSet 进行空检查。
    • 哦，您不需要为每个 it.next() 构造一个新的哈希集 - retainAll 适用于集合，并且 it.next() 中的重复元素不会影响操作。
    • 编辑：我想对于某些retainAll情况有一些节省，但在这种特殊情况下，自定义方法可能无论如何都是有序的。
    • @Carl：如果我在列表本身上使用retainAll，它会增加时间复杂度。当 Y 是一个简单的 List 实现时，X.retainAll(Y) 在 O(|X|*|Y|) 时间内工作。当 Y 为 HashSet 时，它的工作时间平均为 O(|X|)，所以复制是值得的。

    您必须更改第 1 步：
    - 使用最短列表而不是您的 hashSet(如果它不在最短列表中，则它不在所有列表中......)

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

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

    一些代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    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));

        }

    }

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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);`

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

    1
    counter.addAll(list) => counter.addAll(Sets.newHashSet(list))

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

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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    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 集合具有更有效的纯整数结构。

    • 这是 Ankurs 第一个解决方案的可怕突变，为地图中的每个列表创建一个新的 HashSet 基本上会导致你浪费一些 O(n^2) 空间。这是java，GC是不确定的。 GC 可以在未知的时间后收集未使用的哈希集，这意味着 O(n^2) 量的内存将坐在那里，分配，但不投入使用。或者换句话说，浪费了。
    • @Rubys：我看不出你从哪里得到 O(n^2)。如果我不清楚 set 是在第一步中创建的。 IE。在整个循环中都是一样的。在步骤 2a 中创建"中间"集是为了加快查找速度(在 retainAll 中)，因为在哈希集中它是(预期的)O(1) 与列表中的 O(n)。
    • 据我们所知，列表和集合永远都不够小，并且在每次迭代中，您都会创建一个新的 HashSet。 hashet 本身将占用内存中的 O(n) 空间。它不是 O(n^2)，那是我的错，它的 O(nm) 空间，其中 n 是最大的列表，m 是原始集合中的列表数。您会看到，在每次迭代中，您都会创建一个新的哈希集，这会花费 O(n) 空间。由于您必须将这些指针放在某处-。因此，在所有 m 次迭代中，您将使用 O(nm) SPACE。时光依旧美好。

    个中找出spanclassnbspalgorithmarraylistjavareporting

    有关关于java：查找出现在一组列表中的每一个中的所有数字的更多相关文章

    1. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

      总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

    2. ruby - 其他文件中的 Rake 任务 - 2

      我试图在一个项目中使用rake，如果我把所有东西都放到Rakefile中，它会很大并且很难读取/找到东西，所以我试着将每个命名空间放在lib/rake中它自己的文件中，我添加了这个到我的rake文件的顶部:Dir['#{File.dirname(__FILE__)}/lib/rake/*.rake'].map{|f|requiref}它加载文件没问题，但没有任务。我现在只有一个.rake文件作为测试，名为“servers.rake”，它看起来像这样:namespace:serverdotask:testdoputs"test"endend所以当我运行rakeserver:testid时

    3. ruby-on-rails - Ruby net/ldap 模块中的内存泄漏 - 2

      作为我的Rails应用程序的一部分，我编写了一个小导入程序，它从我们的LDAP系统中吸取数据并将其塞入一个用户表中。不幸的是，与LDAP相关的代码在遍历我们的32K用户时泄漏了大量内存，我一直无法弄清楚如何解决这个问题。这个问题似乎在某种程度上与LDAP库有关，因为当我删除对LDAP内容的调用时，内存使用情况会很好地稳定下来。此外，不断增加的对象是Net::BER::BerIdentifiedString和Net::BER::BerIdentifiedArray，它们都是LDAP库的一部分。当我运行导入时，内存使用量最终达到超过1GB的峰值。如果问题存在，我需要找到一些方法来更正我的代

    4. ruby-on-rails - Rails 3 中的多个路由文件 - 2

      Rails2.3可以选择随时使用RouteSet#add_configuration_file添加更多路由。是否可以在Rails3项目中做同样的事情？ 最佳答案 在config/application.rb中:config.paths.config.routes在Rails3.2(也可能是Rails3.1)中，使用:config.paths["config/routes"] 关于ruby-on-rails-Rails3中的多个路由文件，我们在StackOverflow上找到一个类似的问题

    5. ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2

      我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123

    6. ruby-on-rails - Rails - 一个 View 中的多个模型 - 2

      我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何

    7. ruby-on-rails - Rails 3.2.1 中 ActionMailer 中的未定义方法 'default_content_type=' - 2

      我在我的项目中添加了一个系统来重置用户密码并通过电子邮件将密码发送给他，以防他忘记密码。昨天它运行良好(当我实现它时)。当我今天尝试启动服务器时，出现以下错误。=>BootingWEBrick=>Rails3.2.1applicationstartingindevelopmentonhttp://0.0.0.0:3000=>Callwith-dtodetach=>Ctrl-CtoshutdownserverExiting/Users/vinayshenoy/.rvm/gems/ruby-1.9.3-p0/gems/actionmailer-3.2.1/lib/action_mailer

    8. ruby-on-rails - Rails 应用程序中的 Rails : How are you using application_controller. rb 是新手吗？ - 2

      刚入门rails，开始慢慢理解。有人可以解释或给我一些关于在application_controller中编码的好处或时间和原因的想法吗？有哪些用例。您如何为Rails应用程序使用应用程序Controller？我不想在那里放太多代码，因为据我了解，每个请求都会调用此Controller。这是真的？ 最佳答案 ApplicationController实际上是您应用程序中的每个其他Controller都将从中继承的类(尽管这不是强制性的)。我同意不要用太多代码弄乱它并保持干净整洁的态度，尽管在某些情况下ApplicationContr

    9. ruby-on-rails - form_for 中不在模型中的自定义字段 - 2

      我想向我的Controller传递一个参数，它是一个简单的复选框，但我不知道如何在模型的form_for中引入它，这是我的观点:{:id=>'go_finance'}do|f|%>Transferirde:para:Entrada:"input",:placeholder=>"Quantofoiganho?"%>Saída:"output",:placeholder=>"Quantofoigasto?"%>Nota:我想做一个额外的复选框，但我该怎么做，模型中没有一个对象，而是一个要检查的对象，以便在Controller中创建一个ifelse，如果没有检查，请帮助我，非常感谢,谢谢

    10. ruby - RVM 使用列表[0] - 2

      是否有类似“RVMuse1”或“RVMuselist[0]”之类的内容而不是键入整个版本号。在任何时候，我们都会看到一个可能包含5个或更多ruby的列表，我们可以轻松地键入一个数字而不是X.X.X。这也有助于rvmgemset。 最佳答案 这在RVM2.0中是可能的=>https://docs.google.com/document/d/1xW9GeEpLOWPcddDg_hOPvK4oeLxJmU3Q5FiCNT7nTAc/edit?usp=sharing-知道链接的任何人都可以发表评论

    随机推荐