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

Question

我有这个方法可以将 2 个 排序数组 合并为一个 排序数组 :

    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 数组一次完成。

我花了很长时间想出一个解决方案，但没有真正成功。有人知道怎么做吗？

Answer 1

使用 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

Answer 2

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

问题中提供的代码使用了泛型。但是它引入了一个问题，因为数组不是 type-safe。简而言之，它们的行为有很大的不同：数组是协变，而另一方面，泛型是不变。因此，当泛型和数组混合使用时，编译器将无法识别问题。避免使用通用数组是一个好习惯。

此外，我已经考虑到这显然是一个算法问题（因此它的受众比对 Java 有深刻见解的读者更广泛，这需要掌握 generic-based 实现) 我决定创建两种解决方案，一种专门使用数组，另一种使用泛型和集合框架。

Non-generic版本

下面是如何合并任意数量的已排序基元数组的说明：

找到元素总数并根据它创建结果数组；
定义一个数组，该数组将在每个源数组中保持当前位置；
对结果数组中的每个位置使用嵌套 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]

普通版

在此版本中，输入被视为一个 list，其中包含多个 list 的泛型类型 T，预计将实现Comparable界面。

此解决方案增强了上面提供的 array-based 实现，将整体时间复杂度降低到 O(n * log m)（其中 n - 是所有数组中元素的总数，m是数组的个数）。

它维护一个 PriorityQueue，而不是对每个结果元素执行 m 迭代，在这种情况下代表 Min-Heap（即当从中检索头元素时，它将具有 queue).

中存在的所有元素的最低值

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

嵌套列表元素的包装可以用下面显示的 class 来表示。

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());
    }
}

请注意，此 class 基于包装列表元素的 value 实现了 Comparable 接口。

正在使用每个 non-empty 列表的第一个元素预填充队列。然后直到队列不为空，它的最低元素被删除并添加到结果列表中。此外，如果从队列中检索到的最新元素指向的列表有更多元素，则下一个元素将被添加到队列中。

注意根据[=34=向优先级队列add()添加新元素和移除头元素remove()这两个操作] 的成本为 O(n) 时间（其中 n 是队列中的元素数）。

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

代码可能如下所示：

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]

Answer 3

我不是 Java 程序员所以我只给出 Pythonesque pseudo-code.

先把每个non-emptyarray变成三联体：

(next_value, index, array)

现在将它们放入 priority queue 按下一个值排序。

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(...) 如果可以的话会让你用 [= 遍历那些运行 17=] 每个元素工作。

Answer 4

除了 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]

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

Merging 4 sorted Arrays into one

java

arrays

sorting

algorithm

array-merge

Non-generic版本

普通版