Реализация итератора для k отсортированных массивов без дубликатов - вопрос для интервью

Question

Первая часть вопроса была:
Учитывая 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() + " ");
        }

    }
}

Answer 1

Вы можете сделать это намного проще, используя 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());
}

Answer 2

Я думаю, что небольшая модификация вашего исходного кода устранит дубликаты:

1. Когда вы создаете итератор, сохраняйте элемент max всех массивов (вам придется проверитьпоследний элемент каждого из k массивов, чтобы найти максимум).

2. Также сохраните элемент, возвращенный последним вызовом, в next().Это может быть инициализировано в Integer.MIN_VALUE и изменено в каждом вызове на next().

3. hasNext() просто проверяет, вернул ли последний элемент

4. Новый 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;
}