Chinaunix

标题: 取最小空档 [打印本页]

作者: joepayne 时间: 2013-07-05 09:35
标题: 取最小空档
有一组连续存储的值 arr[] = {3,4,5,8,9,10,1,2,6};
这组数字的规则是这样的，当前数字的值是前面所有值中的最小的空档，如果前面没有空档则在最大值的基础上加1。
删除的时候，可以随机删，删除之后数据要挪动。
例如
第一次插入后序列：1
第二次插入后序列：1，2
第三次插入后序列：1，2，3
第四次插入后序列：1，2，3，4
第五次删除2后序列：1，3，4
第六次插入后序列：1，3，4，2
第七次插入后序列：1，3，4，2，5
第八次插入后序列：1，3，4，2，5，6
第九次删除4后序列：1，3，2，5，6
第十次删除3后序列：1，2，5，6
第十一次插入后序列：1，2，5，6，3
。。。
第N次插入的时候当前值取多少？

作者: leejqy 时间: 2013-07-05 17:29
本帖最后由 leejqy 于 2013-07-05 17:33 编辑

小根堆。
将当前最小空挡丢入丢堆中，
1.如果删除某个值，则将这个值丢入堆中；
2.如果插入，则从堆中取最小值（小跟堆），如果第n次取时堆空，说明前面所有n-1个数都利用了，所以直接是n；

作者: joepayne 时间: 2013-07-08 09:08

小根堆

谢谢，小弟试试看！敢问，大神了解内核对单进程内系统资源－－文件描述字的维护也如此算法吗？因为我突然记起来好像文件描述字的获取与回收似乎也是这个规律。{:3_183:}

欢迎光临 Chinaunix (http://bbs.chinaunix.net/)