除非您在任何给定时间仅允许集合中的项目的一个实例,否则即使集合已排序,也不可能在恒定时间内知道集合中有多少个唯一项目.如果你确实将集合限制为只有独特的项目,那么答案是微不足道的; 它是集合中的项目数量,因为它们都必须是不同的.
如果您有一个有序的非不同项集合,您可以通过迭代集合并查找状态更改(当前值与前一个值不同时)找到不同项目的数量.不同项目的数量比状态更改的数量多一个(或者,如果以"空"状态开始,则将状态更改的数量计为一个,并将第一个项目作为更改计数).
您还可以扩充数据结构并添加/删除算法以跟踪集合中不同项目的数量,这样您只需查询在添加/删除期间更新的值,即可在恒定时间内"找到"此数字.这应该不会影响效率要么因为你只需要确定,在添加,新项目是否是第一它的类型通过检查前一个/下一个项目有相同的键,并删除,是否已删除的项目通过相同的检查是它的类型的最后一项.
让我们考虑一个简单的例子.
假设你有一个神奇的包包含几个不同颜色的块,编号从1到N.这个包很神奇,因为每当你进入包中,你可以确定包中有多少个块(N的值)或者看一个阻止保证每次进入块时,您将获得颜色顺序的下一个块,所有红色,所有绿色等等,直到不再剩下或者您可以通过其编号检查任何单个块.你想要的是通过固定次数进入袋中找出袋中有多少种不同颜色的块.
现在,获取包中的总块数需要一个范围,但是你没有好处,因为你想知道不同颜色的数量.获得任意数量的随机选择的块(小于N)需要固定数量的到达,但是你没有好处,因为他们没有告诉你任何关于包中其余块的信息.你唯一能做的就是按顺序逐个拉出所有的块,找到下一个块与上一个块颜色不同的次数.
现在,如果你允许我改变把块放入袋中或从袋中取出的方法,我可以随时跟踪袋中有多少块颜色,然后告诉你再次变得微不足道.我只是告诉你我正在追踪的价值.基本上我交易的是一小部分空间(我跟踪价值的地方)以及在添加/删除期间花费一些额外的时间,试图在以后找到不同颜色的数量.你只需要决定权衡是否值得.