取最小空檔

joepayne

有一組連續(xù)存儲(chǔ)的值 arr[] = {3,4,5,8,9,10,1,2,6};
這組數(shù)字的規(guī)則是這樣的，當(dāng)前數(shù)字的值是前面所有值中的最小的空檔，如果前面沒有空檔則在最大值的基礎(chǔ)上加1。
刪除的時(shí)候，可以隨機(jī)刪，刪除之后數(shù)據(jù)要挪動(dòng)。
例如
第一次插入后序列：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次插入的時(shí)候當(dāng)前值取多少？

leejqy

小根堆。
將當(dāng)前最小空擋丟入丟堆中，
1.如果刪除某個(gè)值，則將這個(gè)值丟入堆中；
2.如果插入，則從堆中取最小值（小跟堆），如果第n次取時(shí)堆空，說明前面所有n-1個(gè)數(shù)都利用了，所以直接是n；

joepayne

小根堆

謝謝，小弟試試看！敢問，大神了解 內(nèi)核對(duì)單進(jìn)程內(nèi)系統(tǒng)資源－－文件描述字的維護(hù)也如此算法嗎？  因?yàn)槲彝蝗挥浧饋砗孟裎募�描述字的獲取與回收似乎也是這個(gè)規(guī)律。{:3_183:}