一个简单而有用的数据结构

    Hash表是一个很有用的数据结构,它用O(N)的空间描述一个元素在0到N-1范围内的集合,支持常数级别的添加、删除和查询。遗憾的是,Hash表不能在常数时间内批量删除元素,返回全部元素也需要O(N)的时间,而理论上说这几个操作可以做的更好。现在,你能否设计一个数据结构,它同样占用O(N)的空间,支持常数时间的添加、删除、查询、清空(删除所有元素)、势查询(返回元素个数),以及O(n)时间的元素遍历(其中n表示集合中的元素个数)。


    这个数据结构包含一个整型变量n(表示当前元素个数),以及两个数组members和position,前者用来储存当前集合中的元素,后者是一个长度为N的数组,用来记录每个数在members数组中的什么位置(换句话说position[members[i]] == i总成立)。
    想要查询m是否在当前集合内,只需要看看position[m]是不是在0到n-1的范围内,并且members[position[m]]是否也确实等于m。添加一个元素只需要把新元素放进members[n++],并更新position的相应数据。删除一个元素只需要把该元素移到members队列末尾(让这个元素和members数组的第n个数对换一下位置),同时更新position的相应数据,然后n自减一。清空集合只需要直接令n等于0即可。遍历元素只需要扫描members数组中当前有效的那一段,这显然是O(n)的。变量n就是元素个数,需要查询元素个数时直接返回n就行了。

参考资料:http://www.onebadseed.com/blog/?p=80

36 条评论

发表评论