寻找适当的数据结构 [英] Finding an appropriate data structure

问题描述

我有N个键。

我需要找到一个数据结构，我可以使用以下操作：

$ b $在O（N）

中

在O（1）中找到最小值

删除O（logn）中的中位数

找到n / 2 +我想到使用最小的堆（建筑是O（n），最小是O（1） -

$ b < root）。

然而，我很难找到一种方法来做3和4。

我认为中位数假设是在叶子上，但是就我所达到的而言。

解决方案

数据结构1个考试/ hws / tutorials。
我会尝试给你一些提示，如果他们不够，评论，我会给你更多的提示。

1. 请记住，您不必仅使用一个数据结构，您可以使用多个数据结构。


2. 回想一个中位数的定义：n / 2的数字是较大的数字和n / 2的数字较小


3. 您知道哪些数据结构内置于O（n）中，对它们的复杂操作是O（logn）还是更少？ - 重读这些数据结构的教程幻灯片。


4. 您可以轻松地从1 + 2中单独解决1 + 3，然后考虑合并它们。

I have N keys.

I need to find a data structure which i can do with the following operations :

1. building it in O(N)

2. finding min in O(1)

3. deleting the median in O(logn)

4. finding the n/2+7-th biggest number

I thought about using a minimum heap (building is O(n),minimum is O(1) - root).

however, I'm having hard time finding a way to do 3 and 4.

I think the median suppose to be on of the leaves, but that's as far as i reached.

解决方案

A popular question asked in Data Structures 1 exams/hws/tutorials. I'll try to give you some hints, if they don't suffice, comment, and I'll give you more hints.

1. Remember that you don't have to use just one data structure, you can use several data structures.
2. Recall the definition of a median: n/2 of the numbers are larger, and n/2 of the numbers are smaller
3. What data structures do you know that are built in O(n), and complex operations on them are O(logn) or less? - Reread the tutorials slides on these data structures.
4. It might be easier for you to solve 1+3 seperately from 1+2, and then think about merging them.

这篇关于寻找适当的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！