algorithm - 在 O(logN) 时间复杂度中使用 HashMap 对节点链表进行二进制搜索

Question

您能否在 O(logN) 的时间复杂度内对已排序的节点(对象)链表进行二分查找？我知道链表不支持直接索引，所以你不能做像 list[3] 或 list.get(3) 这样的事情，所以基本上你需要遍历列表的所有元素来找到索引中间元素。但是如果你有一个额外的数据结构供你使用，比如 HashMap(key = index,value = node) 呢？这行得通吗？

例子: 假设我们有列表:

1 -> 4 -> 7 -> 9 -> 14 -> 18

以及用于在 O(1) 中获取节点的 HashMap:

0 -> 1
1 -> 4
2 -> 7
3 -> 9
4 -> 14
5 -> 18

现在如果我们想找到 14 个，我们会这样做:

binarySearch(0,5) : middle = 2 -> get node 7 from the Hashmap. 14 > 7 so ->
binarySearch(3,5) : middle = 4 -> get node 14 from the Hashmap. 14 == 14 ->Voila

当然，要构建此 HashMap ，您必须执行 N 次操作，因此时间复杂度为 O(N)，但如果您已经拥有 HashMap ，这可行吗？

如果是，您不能使用这种方法在 O(nlogn) 时间复杂度内对带有附加 HashMap 的链表进行插入排序吗？

基本上:

 1. for each element ( O(n) )
    2. find the position of the element in the list in O(logN) with binary search that uses the Hashmap to get the element at the middle position in O(1).
    3. insert the element in the Linked List in O(1)
    4. insert the (index,element) into the Hashmap in O(1)

---

O(nlogn) 时间复杂度。还是我在做/假设出了什么问题？

Answer 1

这个想法非常好，以下是如何让它发挥作用:作为键，您可以使用节点的值。如果列表节点值是唯一的，那么您可以使用一个节点作为 HashMap 的值(否则是一个节点列表)。所以你仍然可以像往常一样在列表中从一个节点到另一个节点，但你也可以在 O(1) 中按值访问。

如果值在插入和删除时发生变化，您将不得不更新 HashMap ，但一切都是 O(1) 或 O(c)，其中 c 是列表中重复值的最大数量，如果 c 没有t 依赖于 n 那么它是 O(1) 即使重复，否则 O(n)。