1

我试图找出一种方法来有效地将标记为 A1 的 n 个数组合并到 An 。

每个数组 Ai 是 的子集{1..i}。例如，A3 可以是 {1} 或 {3} 或 {1,3}。请注意，每个数组都是排序的。

例如n = 8, A1={}, A2={2}, A3={2,3}, A4={1,4}, A5=A6=A7={}, A8={6}，将它们全部合并会得到 {1,2,3,4,6}。

我试图找出一种比 O(n^2) 更快的方法，这很明显，因为所有数组中有 O(n^2) 个元素，我们可以创建一个大小为 n 的数组和尝试将每个元素放入一个桶中。

4

2 回答 2

0

您需要一个容器来保存数组的k第 th 项index和 index 。iik

public class Node {
    int item, arrIndx, itemIndx;
    public Node(int a, int b, int c) {
        this.item = a;
        this.arrIndx = b;
        this.itemIndx = c;
    }
}

使用 minHeap（保持按升序对其元素进行排序的优先级队列）来包含Node.

首先，对于每个数组，将其第一个元素推入 minHeap。minHeap 如何保存第一个n排序的元素。

现在从minHeap中一个一个地弹出所有数组项中最小的最前面的元素，并将其放入输出数组中。在弹出 th 数组的任何第kth 元素时，将 th 数组的第 th 元素放入队列中。这样我们可以确保，我们正在推动当前最小元素的直接最小元素。ik + 1i

继续此过程，直到所有数组元素都从 minHeap 中推送和弹出。

示例 Java 代码段将如下所示：

public List<Integer> mergekSortedArrays(int[][] arrays) {

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

    if (arrays == null || arrays.length == 0) {
        return result;
    }

    PriorityQueue<Node> minHeap = new PriorityQueue<Node>(arrays.length,
        new Comparator<Node>() {
            public int compare(Node lhs, Node rhs) {
                return lhs.item - rhs.item;
            }
        }
    );

    // O(n log n)
    for (int i = 0; i < arrays.length; i++) {
        if (arrays[i].length > 0) {
            minHeap.offer(new Node(arrays[i][0], i, 0));
        }
    }

    Node node;

    // O((N - n)log n)
    while (!minHeap.isEmpty()) {
        node = minHeap.poll();
        result.add(node.item);
        if (node.itemIndx + 1 < arrays[node.arrIndx].length) {
            minHeap.offer(new Node(arrays[node.arrIndx][node.itemIndx + 1], node.arrIndx, node.itemIndx + 1));
        }   
    }

    return result;

}

时间复杂度是O(N log n)数组n的N数量和这些数组中所有元素的数量。

于 2016-11-16T15:26:08.897 回答
0

如果您已经k对包含项目总数的整数数组进行了排序n，那么您可以使用 O(k) 额外空间在 O(n log k) 时间内将它们合并。这是如何完成的：

首先，创建一个名为 的类型pqitem，它保存一个数组和数组的当前索引。例如：

class pqitem
    int[] A;
    int i;

然后，创建一个优先级队列（最小堆）来保存pqitem实例。比较函数应该 compare A[i]，所以堆中的项目被排列，使得当前项目最小的数组位于根。

对于每个数组，创建一个pqitem实例来保存数组。将该字段初始化i为 0。插入优先级队列。

现在，不断地从堆中移除最低的项，输出当前值，增加i，然后将该项重新添加到堆中i < A.length。那是：

myHeap = new heap()
for each array
    item = new pqitem(array, 0)
    myHeap.Add(item)

while (myHeap.count > 0)
    item = myHeap.pop()
    output item.A[item.i]  // output or add to new array, etc.
    ++item.i
    if (item.i < item.A.length)
        myHeap.Add(item)

在您的情况下，您希望防止重复。因此，您稍微修改合并循环以跟踪最后一项输出，并防止输出重复项。

// keep track of the previous item
prev = -1  // Initialize to a value that won't appear in the lists
while (myHeap.count > 0)
    item = myHeap.pop()
    // skip duplicates
    if (item.A[item.i] != prev)
        output item.A[item.i]  // output or add to new array, etc.
        prev = item.A[item.i]
    ++item.i
    if (item.i < item.A.length)
        myHeap.Add(item)
于 2016-11-16T15:22:35.940 回答