This question already has an answer here:
Given K sorted lists of up to N elements in each list, return a sorted iterator over all the items

(1个答案)


2年前关闭。




我发现以下面试问题here.

SortedIterator-由列表列表组成,列表中具有排序的int值
每个列表。调用next()时必须提供下一个排序的值。

必须实施方法
*构造函数
* 下一个()
* hasNext()

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

next()-> 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)

空格:O(N * K)存储展平的列表。

N-列表数。

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

但是链接中的answer表示:

有一个使用优先级的时间复杂度为O(logN)的解决方案
队列。也许一个面试官期望这样的事情,我不
知道。
O (log N)怎么可能?如果使用了优先级队列,则每次调用hasNext()时,我们都需要检查队列是否为空(O(1))。然后我们调用next(),它根据table从队列中提取min元素(对于任何实现,都是O(log (N*K))。由于我们需要调用next() N * K次,因此需要O(N * K * log (N*K)来迭代所有元素。

最佳答案

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

解决方案如下所示:

  • 首先定义一个名为ListValue的新类,该类存储值以及它来自的列表的索引。这些应该与使用该值的其他ListValue对象相当。
  • 构造函数:初始化一个称为PriorityQueue<ListValue>pq,并将N个列表中的每个列表的第一个元素放入pq中。
  • next():弹出ListValue前面的pq。内部的值是要返回的值,但首先,将ListValue列表中的下一个元素移到pq中。复杂度为O(log N),因为我们删除了一个元素,然后向pq添加了一个元素,next()最多包含N个元素。

  • 请注意,该解决方案不会一次将所有N * K个值都保留在优先级队列中,而是仅从N个列表中的每一个中获取一个“next”值。因此,优先级队列始终具有(最多)N个元素,因此其操作均为O(log N)。

    要了解为什么这样做,请记住每个列表已经排序,因此最小未使用值必须出现在某个列表的“前部”(不包括已经消耗的值)。然后,请注意,优先级队列恰好包含每个列表的“前”元素-当我们从与删除元素相同的列表中向pq添加元素时,我们强制在pq中发生。因此,ojit_code始终会包含最小的未使用值(直到所有值都用尽)。

    08-25 08:30
    查看更多