时间戳

首页 > 解决方案 > 在 List 和 HashMap 之间使用 retainAll() 函数的时间复杂度是多少？

java - 在 List 和 HashMap 之间使用 retainAll() 函数的时间复杂度是多少？

问题描述

假设我有一个嵌套列表，其中包含 n^2 个元素，并且我有一个 HashMap，其中包含 n^2 个键。我想使用retainAll()函数获取列表和哈希图之间的共同元素。在这种情况下，retainAll() 的时间复杂度是多少？

List<List<Integer> list = new ArrayList<>();
Map<List<Integer>, Integer> hashmap = new HashMap<List<Integer>, Integer>();
list.retainAll(hashmap);

为了获得共同点，我正在使用这个循环，但它有 n^2 的复杂性。

List<List<Integer>> commons = new ArrayList<>();

    for (int i = 0; i < list.size(); i++) {
        if (hashmap.get(list.get(i)) != null) {
            commons.add(list.get(i));
        }
    }

此外，如果您有一个具有更好时间复杂度的算法来获得它们的交集，我需要它。

编辑： 实际上问题是，我有一个大小为 n 的整数列表。但我将该列表划分为子列表，子列表计数变为 n^2。由于我想找出 hashmap 包含每个子列表作为其中的键，因此我使用了 n^2 。但根据我的整个项目，它太大了。我正在寻找降低复杂性的方法。

标签： javaalgorithmarraylisthashmapbig-o

解决方案

好吧，我的意思是，如果您n^2在列表中有项目，那么复杂性就是O(n^2)，尽管这确实是一件很奇怪的事情。通常n是集合的大小，所以retainAll考虑时间复杂度O(n)。

据我所知，不可能有一种算法为此产生更好的时间复杂度。您必须至少迭代一次列表...

你可以做的是切换你的数据结构。阅读更多：用于快速交叉路口操作的数据结构？

推荐阅读