迭代器实现k排序数组没有重复 - 面试问题-Java 学习之路

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

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

我成功实现了这一部分，并在下面编写了代码 .

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

我认为这不会很难 - 只需使用 HashSet 字段，在将它们输入堆时将项添加到此集中，然后将其作为循环实现，当您获得唯一项时终止 .
这种方法的问题在于方法 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() + " ");
        }

    }
}

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

回复于 2024-04-27T06:13:42+08:00

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

创建迭代器时，存储所有数组的最大元素（您必须检查每个 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;
}

回复于 2024-04-27T06:13:42+08:00

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

2 回答

相关问题