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

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)。

这种需求是否可行？有没有人可以根据我的示例提供一个实现方法呢？

- user2467545

---

什么是迭代搜索查询？从未听说过这个术语... - Gene

@ksun 不行。合并是O(kn)，但搜索是O(kn log kn)，这比给定的限制更大。 - Gene

@基因搜索的时间复杂度为O(log kn)，或者每次搜索的时间复杂度为O(log k + log n)。 - Sergey Kalinichenko

@dasblinkenlight 对的，抱歉，打字比思考快了。问题是合并不是O(kn)，而是O(kn log k)。你可以创建一个大小为n的索引，指向kn个项目的列表。在索引上进行二分搜索，然后在k个项目的块内进行搜索。但预处理时间太长了！ - Gene

@dasblinkenlight：不完全是这样。假设 list1 = [0,..,n]，list2 = [n,...,n]，list3 = [n,...,2*n]。当合并时，你可以得到列表 list1 + list2 + list3。如果现在搜索元素 n，则列表1和列表3的结果相差 n 个元素，那么如何在 O(log n) 的时间内找到它们呢？你可以将所有的 n 压缩成单个节点，但仍然无法回答前驱/后继查询（虽然这里没有明确要求，但也可以有效地实现）。 - Niklas B.

Answer 1

这种技术被称为分数级联，听起来非常酷。具体步骤如下：

1. 取列表1。将其中每个第二个元素提取并合并到列表2中。现在，“新的”列表2包含所有其自己的元素和列表1的一半元素。 你要记住哪些是从列表1中提取的，并记录指向列表1的指针。然后从前往后遍历新创建的列表2，在每个元素处添加一个指针，指向你看到的列表1中的最后一个元素和列表2中的最后一个元素。从后往前执行同样的操作。
2. 将包含一半列表1元素的“新”列表2与列表3合并等等。

最终得到的交错结果可能如下：

(来源："你本可以发明分数级联" by Edward Z. Yang)

每个列表元素将有一对指针，以便快速查找某种前驱/后继并找到列表中的位置i - 1。

结果，列表元素的总数仅增加了一个常量因子，但很酷的是现在可以快速查询：

1. 在“新”列表k中进行二进制搜索以查找您的搜索元素。复杂度：O(log n)。现在您已经在原始列表k中找到了该元素，因为您可以在O(1)中找到最初在列表k中的周围元素。
2. 您还可以在O(1)中找到列表k - 1中元素的位置，因为您具有列表k - 1中后继/前驱的指针。因此，您可以在每个其他列表中以O(1)的速度报告结果。

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

如需了解更多信息，您应该阅读博客文章，它有很多可视化插图和额外的解释。

- Niklas B.

---

@SSH：你基本上需要一个“有颜色”的排序数组的概念（类？），每个元素有6个指针。它有两种类型的元素，红色和蓝色的（假设蓝色是从早期列表嵌入的元素）。每个元素都有指向其蓝/红前任/后继的指针，每个蓝色元素都有指向其嵌入列表中索引的指针。通过类似合并的过程（O(n)）将一个数组嵌入另一个数组中，然后通过将列表嵌入彼此来预处理列表。查询过程本身很容易实现。 - Niklas B.

@NiklasB。感谢你提供的链接。我看了视频后尝试进行实现，但过了一段时间之后，我决定放弃了。。:( 看起来对我来说太复杂了，无法将其集成到我的代码库中。 - user2467545

@SSH 我真的很难相信在面试中有人会被要求想出这种东西。 - Niklas B.

@NiklasB。从您上面的评论中，我现在可以理解它有多么复杂 :) ..以及我的面试官期望在现场完成这项任务是多么愚蠢...也许他希望我在某个阶段后解释算法..还不确定..但这个问题仍然萦绕在我的脑海中.. - user2467545

@SSH：我认为这并不正确，真正的源代码通常比伪代码/概念复杂得多。我认为拿笔和纸以及几个示例数组会更容易理解。当箭头在数组之间绘制时，指针就更容易理解了。这里有另一篇文章，可以帮助理解和可视化这个概念。然后你可以考虑如何自己实现它。 - Niklas B.

Answer 2

可能已经有其他人回答了这个问题（我还没有刷新页面）。但是这里有一种合并列表的方法，应该可以在O(hn)时间内完成。我实际上还没有在编辑器中测试过语法，但我认为这个想法应该可行...

调用此方法后，您应该能够在合并后的列表上执行二分搜索。

public static List<Integer> mergeSortedLists(List<List<Integer>> sortedLists){
  List<Integer> mergedList = new List<Integer>();
  int listIndexes[] = new int[sortedLists.size];
  //initialize indexes to 0
  for(int i=0; i<sortedLists.Count(); i++){
    listIndex[i] = 0;
  }  
  int completedLists=0;
  int lowestValue;
  int lowestIndex;
  while(completedLists < sortedLists.Count()){  
    lowestValue = sortedLists[0][listIndexes[0]];
    lowestIndex = 0;
    for(int i=0; i<sortedLists.Count(); i++){      
      int currentIndex = listIndexes[i];      
      List<Integer> currentList = sortedLists[i];
      if(currentIndex >= currentList) continue; //already finished merging this list skip
      int currentValue = currentList[currentIndex];
      if(currentValue < lowestValue){
         lowestValue = currentValue;
         lowestIndex = currentIndex;
      }
    }
    //put the lowest found value into mergedList and increment index
    mergedList.Add(lowestValue);
    listIndexes[lowestIndex]++;
    //if incremented index is equal to increment completed Lists - when all lists are marked
    //complete the while loop will be broken out of and merge should be complete
    if(listIndexes[lowestIndex] == sortedLists[lowestIndex].Count()){
        completedLists++;   
    }
  }
  return mergedList;
}

- ksun

---

嗯...也许这并不会起作用，因为合并的列表没有跟踪值来自哪个列表（如果需要的话）。无论如何...这是值得一试的... - ksun

我认为这不是 O(kn)。它看起来更像是 O(k^2*n)（最终列表将有 k*n 个元素，您需要 k 次迭代才能找到最小值）。通过使用二叉堆在每个步骤中查找最小值，您可以将其降至 O(kn * log k)。 - Niklas B.

Answer 3

由于您的数组已排序，因此元素是可比较的。使用B树结构，并确保数组没有重叠段，即每个数组都已排序，其中任何项都是

item < first 适用于所有其他数组中的所有项；或 item > last 适用于所有其他数组中的所有项。

然后通过比较搜索项（使得first < search item < last），可以实现O(k + logn)的效率；然后在内部进行log(n)搜索。

但本质上这可以是O(logk + logn)。

- Alex Suo