gpt4 book ai didi

c++ - 如何在数字流中找到数字的排名?

转载 作者:塔克拉玛干 更新时间:2023-11-03 04:47:09 25 4
gpt4 key购买 nike

我们有无限的数字流

Input stream --> 3 4 5 8 19 23 3 4 100 4 

任何给定数字的排名将是其右侧较小数字的计数。

Rank of 100 = 1
Rank of right 4 = 0
Rank of middle 4 = 0
Rank of left 4 = 1 (only 3 is smaller than 4)
Rank of 23 = 3 (3,4,4)
Rank of 19 = 3 (3,4,4)
Rank of 8 = 3

我觉得我们可以创建 BST 并使用该特定节点存储排名。你们还有其他解决方案吗?

最佳答案

让我们假设(现在)您正在尝试计算文件中比您小的数字的数量。

暂时假设唯一性,具有此输出的人可以在线性时间内构建一个排序序列(因为他们将获得最终插入位置)。因此,对于 N 个数字的序列,任何基于比较的方法都必须采用 O(NlogN) 来计算此输出。

因此,您真的不能比自平衡树结构做得更好,它为每个步骤提供 logN 保证。

基本算法:您读取、插入、检查位置/距离与开始、输出、重复。

这假设您的树结构为您提供了一个快速/简单的距离/位置度量。树可以很容易地做到这一点,它很容易记账,不幸的是 std::map 没有,所以你需要找到/写一个。

假设问题实际上是相反的,只需将数字存储在一个 vector 中,然后按上述方式处理它们,但顺序相反。

此外,因为它们是数字,所以可能有一种基数/桶排序方法可以比每步 logN 做得更好,尤其是在实际范围很小的情况下。

关于c++ - 如何在数字流中找到数字的排名?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20262064/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com