有效地找到多来分类的列表中的一个元素？ [英] Efficiently find an element in multiple sorted lists?

问题描述

问题陈述： -

我是问这个问题，面试最近..我能拿出低于$ C $仅这为O（K log n）的运行ç -

I was ask this interview question recently.. I was able to come up with the below code only which runs in O(k log n)-

由于K＆LT; = N排序阵列的每个大小为n的，存在需要O（KN）preprocessing，回答迭代搜索查询在O（K + log n）的时间时间和内存的数据结构

Given k <= n sorted arrays each of size n, there exists a data structure requiring O(kn) preprocessing time and memory that answers iterated search queries in O(k + log n) time.

我的K排序的列表，每个大小为n的。目前我有硬codeD 5排序列出每个大小为3，但在一般的，可以是非常高的号 -

I have k sorted Lists, each of size n. Currently I have hard coded 5 sorted Lists each of size 3 but in general that can be very high number-

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

I would like to search for single element in each of the k Lists.

显然，我可以二进制分别搜索每个阵列，这将导致为O（K日志n），其中k是有序阵列的数目。

Obviously, I can binary search each array individually, which will result in O(k log n) where k is number of sorted arrays.

我们能做到这一点的O（K +日志n）其中k为有序阵列的数量？因为我觉得可能是这样做，因为我们正在做同样的搜索k次以现在的一些更好的方式 -

Can we do it in O(k + log n) where k is the number of sorted arrays? As I think there might be some better way of doing it as we're doing the same searches k times as of now -

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);
}

无论输出我看到与我上面的code的做法应该有新的方法，以及应在 0的工作（K + log n）的。

这是可能实现？任何人都可以提供一个例子怎么会在我的例子这项工作的基础？

Is this possible to achieve? Can anyone provide an example how would this work basis on my example?

推荐答案

该技术被称为分数级联这听起来非常酷。你要做的是以下内容：

The technique is called Fractional cascading which sounds very cool. What you do is the following:

1. 以清单1.取它的每一秒元素，并将其合并到列表2.现在的新清单2包含清单1的所有元素，其中一半的人。 你还记得哪些是从清单1和指针回到表1，然后你通过由前至后新创建的列表2，增加了对每一个元素的指针从列表1，你看到的最后一个元素和最后一个元素从表2，你所看到的。从后向前做同样的。
2. 以新名单2半清单1中的元素嵌入和清单3等合并。

1. Take list 1. Take every second element of it and merge it into list 2. Now "the new" list 2 contains all its elements and half of the ones from list 1. You remember which ones are from list 1 and pointers back to list 1 and then you pass through the newly created list 2 from front to back, adding for every element a pointer to the last element from list 1 that you saw and to the last element from list 2 that you saw. Do the same from back to front.
2. Take the "new" list 2 with half of list 1's elements embedded and merge it with list 3 etc.

由此产生的交错会是这个样子：

The resulting interleaving will look something like this:

（来源：你可以发明小数级联爱德华Z.杨）

和每个列表元素都会有几个指针找到predecessors /某一种快速的继任者，并在列表中找到的位置i - 1

and every list element will have a couple of pointers to find predecessors/successors of a certain kind fast and to find the position in the list i - 1.

原来列表中的元素的总数量仅增加一个常数因子，但很酷的事情是，你现在可以做的查询速度快：

Turns out the total number of list elements is only increased by a constant factor, but the cool thing is that you can now do queries fast:

1. 请在新名单为k的二进制搜索找到你的搜索元素。复杂性： O（log n）的。现在发现的原始列表k中的元素，因为你可以在O（1）周围原本在名单k个元素。
找到
2. 您还可以找到在列表k中元素的位置 - 1 O（1），因为你有指向后继/ predecessor在列表ķ - 1。所以，你可以在报告的结果为所有其他列表O（1）每个

1. Do a binary search in "new" list k to find your search element. Complexity: O(log n). You now found the element in the original list k, because you can find in O(1) the surrounding elements that were originally in list k.
2. You can also find the position of the element in list k - 1 in O(1) because you have pointers to the successor/predecessor in list k - 1. So you can report the result for all the other lists in O(1) each

总运行时间： O（日志N + K）

有关详细信息，你一定要阅读博客文章，它有很多可视化插图和额外的解释。

For more information, you should definitely read the blog post, it has lots of visualizing illustrations and additional explanations.

这篇关于有效地找到多来分类的列表中的一个元素？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！