时间戳

首页 > 解决方案 > 没有重复的 k 排序数组的迭代器实现 - 面试问题

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

问题描述

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

如果我们有: a1 = {1,3,5}, a2 = {2,4,4,5}，那么迭代器执行7次的调用next()方法将返回: 1,2,3,4,4,5,5。

我成功实现了这部分，并在下面为它编写了代码。

第二部分是在next()方法不返回重复项时实现这个迭代器类。对于上面示例中的数组，如果我们调用该next()方法5次，我们得到：（1,2,3,4,5如果我们调用它 6 次，我们需要得到一个异常）。

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

你知道如何以一种有效的方式实现这个迭代器而不返回重复项吗？ 

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

    }
}

标签： javaarraysperformanceiteratorpriority-queue

解决方案

我认为对您的原始代码进行小的修改将消除重复：

  1. 创建迭代器时，存储所有数组的最大元素（您必须检查每个k数组的最后一个元素以找到最大值）。

  2. 还将最后一次调用返回的元素存储到next(). 这可以Integer.MIN_VALUE在每次调用时初始化和修改next()。

  3. hasNext()只需检查最后一个元素是否返回 < 最大元素

  4. new重复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;
}

推荐阅读