如何设计一个获取中位数并在 O(1) 中插入的数据结构？
how to design a data structure that getMedian and insert in O(1)?
我考虑过在排序数组中执行此操作并保存中位数的索引及其耗时 O(1)。但我想不出有什么方法可以在 O(1) 中进行插入并保持数组排序。
如果有人能帮我解决这个问题，我真的很感激
你要求的是不可能的，因为它允许在 O(n) 时间内进行基于比较的排序：
- 假设您有一个长度为 n 的未排序数组。
- 在O(n) 时间内找到最小元素和最大元素。
- 将所有 n 个元素插入到数据结构中，每次插入都需要 O(1) 时间，所以这需要 O(n) 时间。
- 插入 n-1 个额外的最小元素副本。这也需要 O(n) 时间。
- 初始化长度为 n 的输出数组。
- 重复 n 次：
- 读出数据结构中当前元素的中位数，并将其写入输出数组的下一个位置。这需要 O(1) 时间。
- 将最大元素的两个副本插入数据结构。这需要 O(1) 时间。
上述算法应该在 O(n) 时间内运行，结果是输入数组中元素的排序数组。但这是不可能的，因为比较排序需要 Ω(n log n) 的时间。因此，假定的数据结构不存在。
我考虑过在排序数组中执行此操作并保存中位数的索引及其耗时 O(1)。但我想不出有什么方法可以在 O(1) 中进行插入并保持数组排序。 如果有人能帮我解决这个问题，我真的很感激
你要求的是不可能的，因为它允许在 O(n) 时间内进行基于比较的排序：
- 假设您有一个长度为 n 的未排序数组。
- 在O(n) 时间内找到最小元素和最大元素。
- 将所有 n 个元素插入到数据结构中，每次插入都需要 O(1) 时间，所以这需要 O(n) 时间。
- 插入 n-1 个额外的最小元素副本。这也需要 O(n) 时间。
- 初始化长度为 n 的输出数组。
- 重复 n 次：
- 读出数据结构中当前元素的中位数，并将其写入输出数组的下一个位置。这需要 O(1) 时间。
- 将最大元素的两个副本插入数据结构。这需要 O(1) 时间。
上述算法应该在 O(n) 时间内运行，结果是输入数组中元素的排序数组。但这是不可能的，因为比较排序需要 Ω(n log n) 的时间。因此，假定的数据结构不存在。