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

Question

问题陈述：-

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

显然，我可以单独对每个数组进行二分搜索，这将得到O（k log n)，其中k是排序数组的数目。

我们能在O(k+logn)中做吗，其中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);
}

这有可能实现吗？谁能提供一个例子，这是如何工作的基础上我的例子？

Answer 1

这种技术叫做分数级联，听起来很酷。您所做的是：

1. 接受列表%1。取其中的每一个元素并将其合并到列表2中。现在“新的”列表2包含了它的所有元素和列表1中的一半元素。您记住哪些是来自列表1的，然后指针返回到列表1，然后从前面到后面穿过新创建的列表2，为每个元素添加一个指针，指向您看到的列表1中的最后一个元素和您看到的列表2中的最后一个元素。从后到前执行相同操作。
2. 使用嵌入列表1元素一半的“新建”列表2，并将其与列表3等合并

由此产生的交错将如下所示：

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

list元素的总数只增加了一个常数,但很酷的一点是,您现在可以快速执行查询：

1. 在“新建”列表k中进行二分搜索以找到您的搜索元素。复杂性:O（log n)。您现在找到了原始列表k中的元素，因为您可以在O(1)中找到原始列表k中的周围元素。
2. 您还可以在O(1)中找到元素在列表k-1中的位置，因为您有指向列表k-1中后继/前置的指针。因此您可以在O(1)each
中报告所有其他列表的结果

运行时总数:O（日志n+k)

要了解更多信息，你绝对应该阅读博文，它有很多可视化的插图和附加的解释。