有效地找到多来分类的列表中的一个元素？

本文介绍了有效地找到多来分类的列表中的一个元素？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

问题陈述： -

我是问这个问题，面试最近..我能拿出低于$ 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?

pointers

有效地找到多来分类的列表中的一个元素？

问题描述

推荐答案