当前位置: 首页 > 面试题库 >

从队列获取O(1)时间的最小值/最大值?

石臻
2023-03-14
问题内容

如何在0(1)时间复杂度的任何时间从队列中检索max和min元素?早些时候,我使用Collections.max和min查找元素,但这将是0(n)。


问题答案:

您只有2种方法来获得最小/最大操作的O(1):

  • 如果结构已排序,并且您知道最大值/最小值位于何处
  • 如果结构未排序且仅允许插入:每次插入项目并分别存储值时,您可以重新计算最小值/最大值
  • 如果结构未排序并且允许插入和删除:我认为您不能做得比O(n)更好,除非您使用多个集合(但该解决方案不支持删除任何元素,仅支持头/尾元素,在队列中应该是这样)。


 类似资料:
  • 我有这样的课: 和类似的列表,其中填充了元素。 如何使用Java8获得的最小值和最大值?

  • 问题内容: 我正在尝试编写一个查询,每天从价格明细表中获取每个商品的最低和最高价格。 在价格明细表中,每天设置多次价格,因此同一日期有很多记录。因此,我想要一个表,其中每个日期都有一行,然后将该表连接到同一张表,因此对于每个不同的日期,我都需要最小值和最大值。 SQL查询 概括 餐桌在同一天设定了许多价格。想要每个交易所报价的每天的最小值和最大值。 谢谢 问题答案: 一个简单的应该工作: 不知道为

  • 问题内容: 我在搜索时遇到问题,只是不知道该怎么做。我的文档具有以下形式: 假设会话ID的第一个时间戳是“登录”,最后一个时间戳是“注销”。我希望所有会话都具有所有“登录”和“注销”文档(如果可能,请按排序)。我设法通过聚合获得正确的时间戳: 但是我如何获得相应的文档?我也不介意我是否必须进行2次搜索(一次用于登录,一次用于注销)。我尝试了热门热门文章的汇总和排序工作,但是我总是会遇到解析错误:/

  • 我试图找到矩阵中每列的最小值和最大值,但我当前的代码运行不正确。我试图把最小值放在一个新矩阵的第一行,最大值放在下一行,并对每一列这样做。任何帮助都将不胜感激,谢谢!

  • 问题内容: 因此,我有一个包含几个列表的列表,这些列表都首先包含三个字符串,然后是一个浮点数,例如: 如何制作一个返回最大值的函数(此处为9.1931)?我试过了 但这只是给我一个清单。 编辑:此外,以任何方式我可以获取值来自何处的索引?喜欢,来自哪个子列表? 问题答案: 循环浏览外部列表,然后选择每个子列表的最后一个元素: 最好将所有与函数相关的变量保留在范围内(将列表作为参数传递,并且不要通过

  • 问题内容: 我有一个像这样的数组: 我需要提取最小和最大的权重值。在这个例子中 $ min_value = 175 $ max_value = 200 有什么帮助吗?谢谢 ! 问题答案: 选项1. 首先,您映射该数组以获取这些数字(而不是全部详细信息): 然后得到最小和最大: 选项2。 (仅当您没有PHP 5.5或更高版本时)与选项1相同,但要选择值,请使用: 选项3。 选项4。 如果您只需要一个