代码之家 › 专栏 › 技术社区 › Miguel

C#SortedSet缺少索引检索O(log[n])

collections data-structures .net c#

Miguel · 技术社区 · 6 年前

HackerRank 解决方案要求:

令我惊讶的是,我意识到没有支持这两种操作的数据结构。

起初,我相信 SortedList

O(对数n) 相对于 O(n)

SortedDictionary和SortedList类之间的另一个区别是,SortedList支持通过键和值属性返回的集合对键和值进行有效的索引检索。在访问属性时不必重新生成列表,因为列表只是键和值的内部数组的包装器。下面的代码显示如何使用Values属性从已排序的字符串列表中对值进行索引检索。

他们建议使用 ToList() 二进制搜索()

O(对数[n]) 这包括向树的每个节点添加一个字段计数,以跟踪在该节点的子树中根目录下有多少项。此字段可以在O(1)中的红黑树旋转期间更新,并且仅使用 sizeof(内部) 每个节点的额外内存。

为什么从一开始就没有这样实施?

把它放在家里有什么坏处 SortedSet 数据结构?

0 回复 | 直到 6 年前

推荐文章

Sneha Sharma · 滑动窗口-在我的代码中找不到错误(非常基本的算法)

2 年前

Eddiex045 · 比较两个文本文件,匹配项转到一个新文件

2 年前

Liferafter · TypeError:缺少1个必需的位置参数(LinkedList)

2 年前

NOBUD · 最大堆插入函数实现C++

2 年前

Tuna ArÄ±yÃ¼rek · “结构对象*对象”和“对象*对象”之间的区别

2 年前

Mark Tyler · 具有O(1)随机移除和添加的数据结构,用于洗牌生成器顺序

6 年前

riasc · 嵌套贴图结构创建空贴图

6 年前

Foxhound013 · 将要发送到视图中的HighCharts的结构化数据

6 年前

Akshay Barpute · cpp中的以下链表程序有什么问题?

6 年前

Batwoman05 · C++中是否有具有类似函数的树集数据结构

6 年前