java - 寻找一种从 2 个列表中查找排序顺序的有效方法

标签 java algorithm

我有 2 组未排序的整数:集合 A 和集合 B。但是我们事先不知道集合 B 中有多少项。

我需要:

while setA and setB are not empty:
    pop the smallest no from setA
    move an int from setB to setA

在 Java 中最有效的方法是什么?

我在想

  1. 为 setA 创建一个 ArrayList,为 setB 创建一个 LinkedList
  2. while (setA 和 setB 不为空) 排序(集合A) 弹出集A 从 setB 中删除一个整数并插入 setA

在 Java 中有更好的方法吗?如果可能,我想删除“在 while 循环中排序”。

最佳答案

TreeSet<Integer> setA = new TreeSet<Integer>(listA);
TreeSet<Integer> setB = new TreeSet<Integer>(listB);
while (!setA.isEmpty()) {
    setA.remove(setA.first());
    if (!setB.isEmpty()) {
        Integer first = setB.first();
        setB.remove(first);
        setA.add(first);
    }
}

说明:TreeSet 类在红黑树中维护集合,该树按照集合元素的自然顺序排序;即本例中的 Integer.compareTo() 方法。添加或删除元素会在树中为该元素找到合适的位置,然后添加或删除它而无需排序。

isEmpty方法是O(1),firstaddremove方法都是O(log N),其中每个都必须被调用 O(N) 次。创建初始树集也是 O(N log N)。因此整体复杂度将为 O(N log N),其中 N 是总列表大小。

关于java - 寻找一种从 2 个列表中查找排序顺序的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1469517/

相关文章:

algorithm - K-Medoids/K-Means 算法。两个或多个聚类代表之间距离相等的数据点

algorithm - 了解支持向量回归(SVR)

algorithm - 比较分水岭和抓取

javascript - 使用 JavaScript,我如何执行将返回多个值的二进制搜索?

java - 这个ejb异常是什么意思?

java - 2 种方式与谷歌日历/Outlook 同步

arrays - 链表如何比插入和删除操作的数组更快,尽管它对两种数据结构都需要 O(n)?

java - Maven + Sonar + Findbugs : Findbugs needs sources to be compiled

java - Android, Canvas ,绘制图像

java - 使用 Java 解析 XML