java - 在多个排序列表中高效地查找元素？

Question

问题陈述:-

我最近被问到这个面试问题..我只能想出下面的代码，它运行在 O(k log n)-

给定 k <= n 个大小为 n 的排序数组，存在一个需要 O(kn) 预处理时间和内存的数据结构，它可以在 O(k + log n) 时间内回答迭代搜索查询。

我有 k 个排序列表，每个列表的大小为 n。目前我已经硬编码了 5 个排序的列表，每个列表的大小都是 3，但通常可以是非常高的数字-

我想在每个 k 列表中搜索单个元素。

显然，我可以分别对每个数组进行二进制搜索，这将导致 O(k log n)，其中 k 是已排序数组的数量。

我们能否在 O(k + log n) 中做到这一点，其中 k 是排序数组的数量？正如我认为可能有一些更好的方法来做到这一点，因为我们现在正在做 k 次相同的搜索 -

private List<List<Integer>> dataInput;

public SearchItem(final List<List<Integer>> inputs) {
    dataInput = new ArrayList<List<Integer>>();
    for (List<Integer> input : inputs) {
        dataInput.add(new ArrayList<Integer>(input));
    }
}

public List<Integer> getItem(final Integer x) {
    List<Integer> outputs = new ArrayList<Integer>();
    for (List<Integer> data : dataInput) {
        int i = Collections.binarySearch(data, x); // binary searching the item
        if (i < 0)
            i = -(i + 1);
        outputs.add(i == data.size() ? null : data.get(i));
    }
    return outputs;
}

public static void main(String[] args) {
    List<List<Integer>> lists = new ArrayList<List<Integer>>();

    List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(3, 4, 6));
    List<Integer> list2 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    List<Integer> list3 = new ArrayList<Integer>(Arrays.asList(2, 3, 6));
    List<Integer> list4 = new ArrayList<Integer>(Arrays.asList(1, 2, 3));
    List<Integer> list5 = new ArrayList<Integer>(Arrays.asList(4, 8, 13));

    lists.add(list1);
    lists.add(list2);
    lists.add(list3);
    lists.add(list4);
    lists.add(list5);

    SearchItem search = new SearchItem(lists);
    System.out.println(dataInput);

    List<Integer> dataOuput = search.getItem(5);

    System.out.println(dataOuput);
}

无论我在上面的代码方法中看到什么输出，新方法也应该在 O(k + log n) 中工作。

这有可能实现吗？任何人都可以提供一个示例，该示例如何基于我的示例工作？

Answer 1

该技术称为 Fractional cascading这听起来很酷。你要做的是:

1. 获取列表 1。每隔一个元素将其合并到列表 2 中。现在"new"列表 2 包含其所有元素和列表 1 中的一半元素。你记得哪些来自列表 1 和指向列表 1 的指针，然后你从前到后遍历新创建的列表 2，为每个元素添加一个指针，指向你看到的列表 1 中的最后一个元素和最后一个元素从您看到的 list 2 中。从后往前做同样的事情。
2. 采用嵌入了列表 1 一半元素的"new"列表 2，并将其与列表 3 等合并。

生成的交错看起来像这样:

(来源:"You could have invented fractional cascading" by Edward Z. Yang)

并且每个列表元素都会有几个指针来快速找到某种类型的前任/后继者，并找到列表 i - 1 中的位置。

原来列表元素的总数只增加了一个常数因子，但很酷的是你现在可以快速查询:

1. 在"new"列表 k 中进行二进制搜索以找到您的搜索元素。复杂度:O(log n)。你现在找到了原始列表 k 中的元素，因为你可以在 O(1) 中找到最初在列表 k 中的周围元素。
2. 您还可以在 O(1) 中找到列表 k - 1 中元素的位置，因为您有指向列表 k - 1 中后继/前任的指针。因此您可以报告结果对于 O(1) 中的所有其他列表，每个

总运行时间:O(log n + k)

有关更多信息，您绝对应该阅读 blog post ，它有很多形象化的插图和额外的解释。