混合两个通用列表 Java

Question

我有一个任务，需要编写一个方法来混合两个泛型列表并返回一个新的混合列表。混合列表应该将l1的第一个元素放在新混合列表的第一个位置，l2的第一个元素应该在第二个位置，然后是l1的第二个元素在第三个位置，以此类推。如果一个列表比另一个列表长，剩下的元素应该按照原始顺序添加。例如：l1 = (1,2,3) 和 l2=(9,8) --> 混合列表 = (1,9,2,8,3)。

public <S, T> List<T> listeMischen(List<S> l1, List<T> l2) {
    List<T> newlist = new ArrayList<T>();
    for(int i = 0; i < l1.size(); i++)
    { 
        for(int j = 0; j < l2.size(); j++) {
            newlist.add(charAt(i));
            newlist.add(charAt(j));
        }           
    }
    return newlist;
}

附言：我不知道如何正确添加元素，因为它们是通用的。我已经输入了完全错误的“charAt”方法，只是为了展示如果类型不是通用的而是字符，我会尝试做什么。 由于元素可以是通用的，我非常不确定该怎么办。

- John_Doe

---

你的返回列表必须是类型T吗？如果是这种情况，那么意味着S是T的子类。如果不是这种情况，我想最好的方法是返回一个Object列表（或者如果存在这样的超类，则返回其超类，该超类同时也是S和T的超类）。 - François Dupire

这两个列表的类型总是相同的吗？ - Ousmane D.

此外，请注意您的算法不会做出您想要实现的功能。您应该从0到较小的列表大小进行第一次循环。然后，您可以有两个循环从该大小到每个列表的末尾，使用剩余元素完成结果列表（不知道我是否清楚 :-P）。 - François Dupire

我可以建议您在方法名称中使用“zip”...您的合并方式就像“拉上/拉下拉链”一样。 - Valentin Ruano

这确实是一个好名字。然而，我住在德国，我的讲师想让我使用这个名字 :) - John_Doe

Answer 1

这将返回两个参数列表的通用超类型的列表：

public <R, S extends R, T extends R> List<R> listeMischen(List<S> l1, List<T> l2) {
    List<R> newList = new ArrayList<>(l1.size() + l2.size());
    int sizeOfLargerList = Math.max(l1.size(), l2.size());
    for (int i = 0; i < sizeOfLargerList; i++) {
        if (i < l1.size())
            newList.add(l1.get(i));
        if (i < l2.size())
            newList.add(l2.get(i));
    }
    return newList;
}

使用方法：

public static void main(String[] args) {
    List<Number> list = listeMischen(Arrays.asList(1, 2, 3), Arrays.asList(4.5, 5.5, 6.5, 7.5, 8.5));
    System.out.println(list);
}

期望输出 == 实际输出:

[1, 4.5, 2, 5.5, 3, 6.5, 7.5, 8.5]

---

更新: 根据评论添加优化方法

以下展示了该方法的两个重载版本：一个用于随机访问列表（如ArrayList），另一个用于任何旧的可迭代类型，并针对每种类型进行了优化。

static <R> List<R> listeMischen(List<? extends R> l1, List<? extends R> l2) {
    if (!(l1 instanceof RandomAccess && l2 instanceof RandomAccess))
        return listeMischen((Iterable<? extends R>) l1, (Iterable<? extends R>) l2);

    // Preallocate with known exact required capacity
    List<R> newList = new ArrayList<>(l1.size() + l2.size());
    int sizeOfSmallerList = Math.min(l1.size(), l2.size());
    int i;
    // Zip the lists up to common maximum index
    for (i = 0; i < sizeOfSmallerList; i++) {
        newList.add(l1.get(i));
        newList.add(l2.get(i));
    }
    // Add any remaining items from one or the other list
    for (; i < l1.size(); i++)
        newList.add(l1.get(i));
    for (; i < l2.size(); i++)
        newList.add(l2.get(i));
    return newList;
}

static <R> List<R> listeMischen(Iterable<? extends R> l1, Iterable<? extends R> l2) {
    List<R> newList = new ArrayList<>();
    Iterator<? extends R> it1 = l1.iterator();
    Iterator<? extends R> it2 = l2.iterator();
    // Zip the lists up to common maximum index
    while (it1.hasNext() && it2.hasNext()) {
        newList.add(it1.next());
        newList.add(it2.next());
    }
    // Add any remaining items from one or the other lists
    it1.forEachRemaining(newList::add);
    it2.forEachRemaining(newList::add);
    return newList;
}

- DodgyCodeException

---

可能更有效率的方法是先循环最小列表长度，而不需要在循环中使用if和重复调用lx.size()，然后如果有任何一个列表剩余，就使用if { for () } -else-if { for () }添加。 - Valentin Ruano

@ValentinRuano 是正确的。另外，我可以使用 .hasNext() 来代替 List.size()（就像 OldCurmudgeon 的回答一样）。 - DodgyCodeException

有限制类型参数的使用很好（+1）。 - Stuart Marks

另一个观察...实际上，你不需要声明类型参数S和T...你可以将l1和l2参数声明为List<? extends R>。我猜这样做没有什么坏处，但是我认为?更可取（更简洁）。 - Valentin Ruano

感谢所有的评论。为了实现最佳性能，我们需要两个版本：一个用于随机访问列表（例如ArrayList），另一个用于非随机访问列表（例如LinkedList）。请注意，ArrayList 实现了 RandomAccess 标记接口，就是为了这个目的。我上面的代码使用 l1.size() + l2.size() 来预分配结果列表的容量，以避免重新分配。对于链表，size() 可能是 O(n)。因此，在这种情况下最好不要预分配（而是使用 hasNext() 而不是 get(i)）。 - DodgyCodeException

Answer 2

唯一明智的做法是返回一个Object列表。由于您的列表不是同质的（并且没有任何关于列表中两个对象类型之间关系的暗示或明示保证），因此泛型无法帮助。

public List<Object> mixedList(List<?> a, List<?> b) {
    List<Object> result = new ArrayList<>();
    for(int i = 0, j = 0; i < a.size() && j < b.size(); i++, j++) {
        result.add(a.get(i));
        result.add(b.get(j));
    }

    return result;
}

我将按照您指定的方式梳理元素的实际问题留给读者自己练习。这 应该 可以满足两个列表长度相同的情况。

- Makoto

Answer 3

您需要为您的S和T找到一些共同点，无论是S是T，还是反过来，或者两者都是某个U的子类型：

public <S extends T, T> List<T> listeMischen(List<S> l1, List<T> l2) {
    List<T> newlist = new ArrayList<>();
    // i will leave the "adding" logic to you, just for the sake of demonstration that you can add elements of both lists
    newlist.add(l1.get(0));
    newlist.add(l2.get(0));

    return newlist;
}

public <U, S extends U, T extends U> List<U> listeMischen2(List<S> l1, List<T> l2) {
    List<U> newlist = new ArrayList<>();
    // i will leave the "adding" logic to you, just for the sake of demonstration that you can add elements of both lists
    newlist.add(l1.get(0));
    newlist.add(l2.get(0));

    return newlist;
} 

- luk2302

---

啊，好的。我重新看了一遍关于泛型的视频，你说的很有道理。我应该记住这一点。 - John_Doe

Answer 4

假设S和T之间有一个共同类型，您可以使用Iterator轻松完成此操作。

public <S extends T, T> List<T> listeMischen(Iterable<S> l1, Iterable<T> l2) {
    List<T> newlist = new ArrayList<T>();
    Iterator<S> l1i = l1.iterator();
    Iterator<T> l2i = l2.iterator();
    // Consume both while we can.
    while (l1i.hasNext() && l2i.hasNext()) {
        newlist.add(l1i.next());
        newlist.add(l2i.next());
    }
    // Consume whatever remains of the remaining list.
    while (l1i.hasNext()) {
        newlist.add(l1i.next());
    }
    while (l2i.hasNext()) {
        newlist.add(l2i.next());
    }
    return newlist;
}

如果没有通用类型或接口，那么您将不得不使用 List<Object>。

- OldCurmudgeon

Answer 5

其他的回答认为泛型不能被使用，或者结果的类型必须是 List<Object>。更好的回答表明两个输入列表和输出列表之间必须存在某种类型关系。其中最佳的回答是DodgyCodeException's answer (+1)，它使用泛型类型边界要求结果列表的元素是两个输入列表的元素类型的超类型。

我会提供一种替代方案，即结果列表的类型是通过将输入列表的元素进行“转换”得到的，且输入列表的元素类型不需要相互关联，也不需要与结果列表的元素类型有任何直接关系。而是提供函数参数来执行转换。

以下是一个从DodgyCodeException派生的示例，它使用转换函数而不是要求输入和输出之间存在类型关系。

static <T, U, R> List<R> listMerge(List<T> l1, List<U> l2,
                                   Function<? super T, ? extends R> f1,
                                   Function<? super U, ? extends R> f2) {
    int size1 = l1.size();
    int size2 = l2.size();
    int max = Math.max(size1, size2);
    List<R> result = new ArrayList<>(size1 + size2);

    for (int i = 0; i < max; i++) {
        if (i < size1)
            result.add(f1.apply(l1.get(i)));
        if (i < size2)
            result.add(f2.apply(l2.get(i)));
    }

    return result;
}

这使得列表的混合/转换成为可能，例如以下内容：

List<String> list = listMerge(List.of(1, 2, 3), List.of(4.5, 5.5, 6.5, 7.5, 8.5),
                              i -> String.format("0x%x", i),
                              d -> String.format("%.1f", d));

[0x1, 4.5, 0x2, 5.5, 0x3, 6.5, 7.5, 8.5]

各种流压缩方法，例如Guava的Streams.zip，也采用函数式转换方法而不是类型绑定方法。

- Stuart Marks