时间戳

首页 > 解决方案 > 使用优先级队列的排序列表列表的迭代器

java - 使用优先级队列的排序列表列表的迭代器

问题描述

我在这里找到了以下面试问题。

SortedIterator - 由列表列表组成，每个列表中都有排序的 int 值。调用 next() 时必须给出下一个排序值。

必须实现方法 * 构造函数 * next() * hasNext()

[ [1, 4, 5, 8, 9], [3, 4, 4, 6], [0, 2, 8] ]

下一个() -> 0, 1, 2, 3, 4, 4, 4...

我用 Java 写了一个快速实现：

package com.app;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;

public class SortedIterator implements Iterator<Integer> {

    private final List<Integer> mFlattenedList;
    private final Iterator<Integer> mIntegerIterator;

    SortedIterator(final List<List<Integer>> lists) {
        mFlattenedList = flattenLists(lists);
        mIntegerIterator = mFlattenedList.iterator();
    }

    private List<Integer> flattenLists(final List<List<Integer>> lists) {
        final List<Integer> result = new ArrayList<>();
        for (List<Integer> list : lists) {
            for (int value : list) {
                result.add(value);
            }
        }
        Collections.sort(result);
        return result;
    }

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

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

时间： O (K * N) 展平输入列表的列表 + O (N*K) 迭代展平的列表 = O (N * K)

Space: O (N * K) 来存储扁平化列表。

N - 列表的数量。

K - 每个列表中的元素数。

但是来自链接的答案说：

有一个使用优先级队列的时间复杂度为 O(logN) 的解决方案。也许面试官会期待这样的事情，我不知道。

怎么O (log N)可能？如果使用优先队列，每次调用 时hasNext()，都需要检查队列是否为空（O(1)）。然后我们根据表调用next()which 从队列中提取最小元素（O(log (N*K)对于任何实现）。由于我们需要调用N * K 次，因此我们需要遍历所有元素。next()O(N * K * log (N*K)

标签： javaalgorithmdata-structurespriority-queue

解决方案

解决方案的 O(logN) 复杂度是每个元素的复杂度，而不是迭代所有值的复杂度。

解决方案如下所示：

  • 首先定义一个名为的新类ListValue，它存储一个值以及它来自的列表的索引。这些应该与ListValue使用该值的其他对象相当。

  • 构造函数：初始化一个PriorityQueue<ListValue>被调用pq并将 N 个列表中每个列表的第一个元素放入pq.

  • next( ) ：弹出ListValue. pq里面的值是要返回的值，但首先，将ListValue列表中的下一个元素移动到pq. 复杂度为 O(log N)，因为我们删除一个元素并添加一个元素到pq，其中最多包含 N 个元素。

请注意，该解决方案不会一次将所有 N*K 值保留在优先级队列中，仅保留 N 个列表中每个列表中的单个“下一个”值。因此，优先级队列始终（最多）有 N 个元素，所以它的操作都是 O(log N)。

要理解为什么这样做，请记住每个列表已经排序，因此最小未使用值必须出现在某些列表的“前面”（不包括已使用的值）。然后，请注意，优先级队列恰好包含每个列表的“最前面”元素——当我们从与我们删除的元素相同的列表中next()添加一个元素时，我们会强制这种情况发生。pq因此，在任何时候pq都将包含最小的未使用值（直到所有值都用完）。

推荐阅读