无重复的 k 排序数组的迭代器实现 - 面试问题

Question

问题的第一部分是：
给定 k 个排序的数组，实现一个迭代器以按升序迭代数组的元素。例如：

如果我们有：a1 = {1,3,5}, a2 = {2,4,4,5}，那么调用迭代器实现7次的next()方法将会return：1,2,3,4,4,5,5。

这部分我实现成功了，下面写了代码。

第二部分是在 next() 方法不 return 重复时实现此迭代器 class。对于上面例子中的数组，如果我们调用next()方法5次我们得到：1,2,3,4,5（如果我们调用它6次，我们需要得到一个例外）。

我认为这并不难 - 只需使用 HashSet 字段，在将项目输入堆时将项目添加到此集合，然后将 next 实现为一个循环，当您获得唯一项目时终止。
这种方法的问题是 hasNext() 方法效率不高：您将不得不迭代将在以后的调用中插入到堆中的元素，以了解您在将来的调用中实际上具有唯一元素 next()。

您是否知道如何以有效的方式实现这个没有重复 returned 的迭代器？

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.PriorityQueue;

public class ComplexIterator implements Iterator<Integer>{

    private class IndexedArrayValue implements Comparable<IndexedArrayValue> {
        int arrayId;
        int index;
        int value;

        public IndexedArrayValue(int arrayId, int index, int value) {
            this.arrayId = arrayId;
            this.index = index;
            this.value = value;
        }

        @Override
        public int compareTo(IndexedArrayValue other) {
            return this.value - other.value;
        }
    }

    private int[][] lists;
    private PriorityQueue<IndexedArrayValue> minHeap;

    public ComplexIterator(int[][] lists) {
        minHeap = new PriorityQueue<IndexedArrayValue>();
        int numOfLists = lists.length;

        this.lists = lists;
        for (int i = 0; i < numOfLists; i++) {
            minHeap.add(new IndexedArrayValue(i, 0, lists[i][0]));
        }
    }

    @Override
    public boolean hasNext() {
        return !this.minHeap.isEmpty();
    }

    @Override
    public Integer next() {
        if (!hasNext())
            throw new NoSuchElementException();

        IndexedArrayValue indArrVal = minHeap.poll();
        int arrayId = indArrVal.arrayId;
        int index = indArrVal.index;
        int value = indArrVal.value;
        int nextIndex = index + 1;

        if (nextIndex < lists[arrayId].length) {
            minHeap.add(new IndexedArrayValue(arrayId, nextIndex, lists[arrayId][nextIndex]));
        }

        return value;
    }

    public static void main (String[] args) {
        int[] arr1 = { 1, 2, 3 };
        int[] arr2 = { 1, 4 };
        int[] arr3 = { 2, 5, 7, 8 };

        int[][] arrs = new int[][] {arr1, arr2, arr3};

        ComplexIterator it = new ComplexIterator(arrs);
        while (it.hasNext()) {
            System.out.print(it.next() + " ");
        }

    }
}

Answer 1

我认为对您的原始代码稍作修改即可消除重复项：

创建迭代器时，存储所有数组的最大元素（您必须检查每个 k 数组的最后一个元素以找到最大值）。
还存储上次调用 next() 返回的元素。这可以初始化为 Integer.MIN_VALUE 并在每次调用 next().
hasNext() 只是检查返回的最后一个元素是否< max element
新的next()反复调用你原来的next()，直到找到一个比之前返回的元素大的元素。

这是一个修改您的代码的实现（它可能需要一些小的修改来支持边缘情况，例如空输入）：

...
private int max; // the maximum element
private int last = Integer.MIN_VALUE; // the last element returned by next()

public ComplexIterator(int[][] lists) {
    minHeap = new PriorityQueue<IndexedArrayValue>();
    int numOfLists = lists.length;

    this.lists = lists;
    max = lists[0][lists[0].length-1];
    for (int i = 0; i < numOfLists; i++) {
        minHeap.add(new IndexedArrayValue(i, 0, lists[i][0]));
        if (lists[i][lists[i].length-1] > max) {
            max = lists[i][lists[i].length-1];
        }
    }
}

@Override
public boolean hasNext() {
    return last < max;
}

@Override
public Integer next() {
    if (!hasNext())
        throw new NoSuchElementException();

    int value;
    do {
        IndexedArrayValue indArrVal = minHeap.poll();
        int arrayId = indArrVal.arrayId;
        int index = indArrVal.index;
        value = indArrVal.value;
        int nextIndex = index + 1;

        if (nextIndex < lists[arrayId].length) {
            minHeap.add(new IndexedArrayValue(arrayId, nextIndex, lists[arrayId][nextIndex]));
        }
    }
    while (value <= last);
    last = value;

    return value;
}

Answer 2

你可以使用 TreeSet 做的更简单：

public final class UniqueSortedIterator implements 
    Iterator<Integer> {

    private final Iterator<Integer> base;

    public UniqueSortedIterator(int[][] arrays) {
        Set<Integer> set = new TreeSet<>();
        for (int[] array : arrays) {
            for (int item : array) {
                set.add(item);
            }
        }
        this.base = set.iterator();
    }

    @Override
    public boolean hasNext() {
        return this.base.hasNext();
    }

    @Override
    public Integer next() {
        return this.base.next();
    }
}

树集既有独特的元素，又保持自然秩序。简单测试：

int[] first = { 1, 3, 5 };
int[] second = { 2, 4, 4, 5 };
Iterator<Integer> usi = new UniqueSortedIterator(new int[][] { first, second });
while (usi.hasNext()) {
    System.out.println(usi.next());
}

无重复的 k 排序数组的迭代器实现 - 面试问题

Iterator implementaion for k sorted arrays with no duplicates - interview question

java

arrays

performance

iterator

priority-queue