将4个已排序的数组合并为一个

Question

将4个已排序的数组合并为一个

3

我有一个方法来将两个已排序的数组合并成一个已排序的数组:

    public void merge(T[] a, int l1, int r1, T[] b, int l2, int r2, T[] c, int l3) {
        while (l1 < r1 && l2 < r2) {
            if (a[l1].compareTo(b[l2]) < 0) {
                c[l3++] = a[l1++];
            } else
                c[l3++] = b[l2++];
        }

        while (l1 < r1)
            c[l3++] = a[l1++];
        while (l2 < r2)
            c[l3++] = b[l2++];
    }

现在我想一次使用4个数组来完成它。

我尝试了很长时间来想出一个解决方案，但并不成功。是否有人有办法做到这一点？

- Kicksy

我有一个C++的例子，使用嵌套的if else语句来实现4路归并排序，该例子在这个答案中有详细说明。该例子使用指针，但也可以使用索引。如果要处理超过4个数组，可以使用最小堆，但这样会比每次合并4个数组慢。这个C++的例子是使用goto语句的旧代码。对于Java，需要将代码的某些部分复制一份来替代goto语句，并且在降到3路、2路归并和1路复制时需要更多的if语句。 - rcgldr

@Dan，你得出了错误的结论，因为你没有仔细阅读问题。合并N个已排序数组的问题在时间复杂度上与合并未排序数组的任务有很大的不同。多次方法调用会增加内存消耗（因为中间数组），同时需要比较的总数也会更多（即性能会降低）。因此，这个问题是有意义的。 - Alexander Ivanchenko

4个回答

2

我将问题概括为“将N个已排序数组合并为一个已排序数组”。

该问题的代码使用了泛型。但是，这会引入一个问题，因为数组不是类型安全的。简而言之，它们的行为有很大的差异：数组是协变的，而泛型是不变的。由于这个原因，当混用泛型和数组时，编译器无法识别出问题。避免使用泛型数组是一种好的实践。

另外，我考虑到这显然是一个算法问题（因此其受众比那些需要深入了解Java才能掌握基于泛型的实现的读者更广），我决定创建两种解决方案：一种仅使用数组，另一种使用泛型和集合框架。

非泛型版本

下面是如何合并任意数量的原始排序数组的描述：

- 找到所有元素的总数，并基于它创建一个结果数组； - 定义一个数组，用于维护每个源数组中的当前位置； - 对于结果数组中的每个位置，使用嵌套的for循环选择所有当前可访问值中最小的值。

这个算法的时间复杂度是O(n * m)（其中n是所有数组中的元素总数，m是数组数量）。

该实现可能看起来像这样：

public static int[] mergeNSorted(int[]... arrays) {
    int[] result = new int[getTotalLength(arrays)];
    int[] positions = new int[arrays.length]; // position for each array
    
    for (int pos = 0; pos < result.length; pos++) {
        int minCurVal = Integer.MAX_VALUE;
        int curArr = 0;
        for (int i = 0; i < arrays.length; i++) {
            if (positions[i] < arrays[i].length && arrays[i][positions[i]] < minCurVal) {
                minCurVal = arrays[i][positions[i]];
                curArr = i;
            }
        }
        result[pos] = minCurVal;
        positions[curArr]++;
    }
    return result;
}

public static int getTotalLength(int[][] arrays) {
    long totalLen = 0;
    for (int[] arr : arrays) totalLen += arr.length;
    
    if (totalLen > Integer.MAX_VALUE) throw new IllegalArgumentException("total length exceeded Integer.MAX_VALUE");
    return (int) totalLen;
}

main() - 演示

public static void main(String[] args) {
    int[][] input =
        {{1, 3}, {}, {2, 6, 7}, {10}, {4, 5, 8, 9}};

    System.out.println(Arrays.toString(mergeNSorted(input)));
}

输出

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

通用版本

在此版本中，输入被视为包含多个泛型类型为T的列表的列表，这些列表应实现Comparable接口。

该解决方案增强了上面提供的基于数组的实现，将总时间复杂度降至O(n * log m)（其中n是所有数组中元素的总数，m是数组的数量）。

它不是为每个结果元素执行m次迭代，而是维护一个PriorityQueue，在本例中表示一个最小堆（即当从中检索头元素时，它将具有所有存在于队列中的元素中最低的值）。

队列中的每个元素都包装了从给定列表之一检索的特定元素的值，以及关于此值来源的数据（即列表的索引和此列表内部的位置）。

这个嵌套列表的元素包装器可以由下面所示的类来表示。

public class ElementWrapper<V extends Comparable<V>> implements Comparable<ElementWrapper<V>> {
    private V value;
    private int listIndex;
    private int position;
    
    public ElementWrapper(V value, int listIndex, int position) {
        this.value = value;
        this.listIndex = listIndex;
        this.position = position;
    }
    
    // getters
    
    @Override
    public int compareTo(ElementWrapper<V> o) {
        return value.compareTo(o.getValue());
    }
}

注意，该类基于包装列表元素的值实现了Comparable接口。

队列将使用每个非空列表的第一个元素进行预填充。然后，直到队列为空为止，将删除其最低元素并添加到结果列表中。此外，如果从队列中检索的最新元素指向的列表具有更多元素，则将它们中的下一个元素添加到队列中。

请注意，根据文档，将新元素添加到优先级队列add()和删除其头元素remove()的两个操作都需要O(n)时间成本（其中n是队列中元素的数量）。

通过使用TreeSet也可以实现相同的时间复杂度，但实际上PriorityQueue的性能更好，因为维护堆比维护红黑树更容易。

代码可能如下所示：

public static <T extends Comparable<T>> List<T> mergeNSorted(List<List<T>> lists) {
    List<T> result = new ArrayList<>();
    Queue<ElementWrapper<T>> queue = getInitializedQueue(lists);
    
    while (!queue.isEmpty()) {
        ElementWrapper<T> next = queue.remove();
        result.add(next.getValue());
        
        if (next.getPosition() + 1 < lists.get(next.getListIndex()).size()) {
            queue.add(new ElementWrapper<>(lists.get(next.getListIndex()).get(next.getPosition() + 1),
                                           next.getListIndex(),
                                           next.getPosition() + 1));
        }
    }
    return result;
}

public static <T extends Comparable<T>> Queue<ElementWrapper<T>> getInitializedQueue(List<List<T>> lists) {
    Queue<ElementWrapper<T>> queue = new PriorityQueue<>();
    for (int i = 0; i < lists.size(); i++) {
        if (lists.get(i).isEmpty()) continue;
        queue.add(new ElementWrapper<>(lists.get(i).get(0), i, 0));
    }
    return queue;
}

main() - 演示

public static void main(String[] args) {
    List<List<Integer>> genericInput =
        List.of(List.of(1, 3), List.of(), List.of(2, 6, 7), List.of(10), List.of(4, 5, 8, 9));
    
    System.out.println(mergeNSorted(genericInput));
}

输出

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

- Alexander Ivanchenko

1

如果您有k个数组，则每个元素产生O(k)次比较，其中大部分比较是在未更改的值之间进行的。可以做得更好。 - btilly

@btilly，我已经提供了一个运行时间为**O(n * log k)**的实现。 - Alexander Ivanchenko

好的。对于非原始数组，Java将使用Timsort进行排序。如果一个由n个元素组成的数组有k个已排序的运行，则它也可以在O(n * log(k))的时间内进行排序。您需要进行基准测试以找出常数是更好还是更差。 - btilly

1

@btilly，好的，你说服了我，我会花时间来测量性能。 - Alexander Ivanchenko

1

我不是Java程序员，所以我将提供类似Python的伪代码。

首先，将每个非空数组转换为三元组：

(next_value, index, array)

现在将它们放入一个按下一个值排序的优先队列中。

while 0 < queue.size():
    (next_value, index, array) = queue.poll()
    answer.append(next_value)
    if index+1 < array.length:
        queue.add((array[index+1], index+1, array))

如果您有 k 个数组，则每个元素的生产需要 O(log(k)) 次比较。

遗憾的是，Java似乎没有与 swaptop 方法相对应的任何东西。实际上，如果一个数组有一个值运行，使用.peek()获取顶部元素然后.swaptop (...)（如果可以）将让您通过这些运行以每个元素O(1)的工作完成。

- btilly

0

这也可以是一个很好的例子，除了int[]之外，还使用了List<String>

import org.testng.annotations.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;

public class TestClass {

    public static List<String> list(String... elems) {

        return new ArrayList<>(Arrays.asList(elems));
    }

    public static List<String> mergedListSorted(List<String>... listsVarArgs) {

        return Stream.of(listsVarArgs).flatMap(List::stream).sorted().collect(Collectors.toList());
    }

    @Test
    public void sortedListsTest() {

        // Sorted sub lists
        List<String> AGMS = list("A", "G", "M", "S");
        List<String> BHNT = list("B", "H", "N", "T");
        List<String> CIOU = list("C", "I", "O", "U");
        List<String> DJPV = list("D", "J", "P", "V");
        List<String> EKQW = list("E", "K", "Q", "W");
        List<String> FLRX = list("F", "L", "R", "X");

        System.out.println(mergedListSorted(AGMS, BHNT, CIOU, DJPV, EKQW, FLRX));
        System.out.println(mergedListSorted(BHNT, BHNT, CIOU, BHNT));

    }

}

两个例子的相应输出：

[A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X]
[B, B, B, C, H, H, H, I, N, N, N, O, T, T, T, U]

- DFB_Altintop

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- trpouh · Accepted Answer

使用Java8的流比手动操作更简单：

将所有数组组合成一个流（我使用了2个，但您可以根据需要使用任意数量）：

int[] arr1 = {1, 7, 10};
int[] arr2 = {1, 2, 4, 9};

Stream<int[]> ints = Stream.of(arr1, arr2);

然后在流中使用flatMap和sort进行操作：

IntStream intStream = ints.flatMapToInt(Arrays::stream).sorted();

当你打印它们时，你会看到所有的数字都已经排序好了：

intStream.forEach(System.out::println);

1
1
2
4
7
9
10

如果将它们组合到一个函数中，代码可能看起来像这样：

public int[] merge(int[]... arrays) {
  return Stream.of(arrays)
                 .flatMapToInt(Arrays::stream)
                 .sorted()
                 .toArray();
}

编辑：流的优势在于，您可以根据需要进一步修改值。例如，通过利用distinct函数，您可以轻松地删除重复项：

intStream = intStream.distinct();
intStream.forEach(System.out::println);

1
2
4
7
9
10