Skip to content

Latest commit

 

History

History
21 lines (13 loc) · 753 Bytes

ch1.md

File metadata and controls

21 lines (13 loc) · 753 Bytes

#1 The smallest free number

##简介

给定有限个自然数组成的集合X,求不在X中的最小自然数。如果X是有序的,只需要逐个检查。如果X无序,比如:

[08,23,09,00,12,11,01,10,13,07,41,04,14,21,05,17,03,19,02,06]

是否有线性时间的解法?列表的排序不能在线性时间完成(故作排序预处理不是个好想法)。尽管如此,是存在线性复杂度解法的:一个基于Haskell的数组,一个使用分治法

##基于数组的解法 根据题意,有个很直接的解法

minfree :: [a] -> a 
minfree xs = head ([0..] \\ xs) 

"\"接受两个列表参数xs,ys,结果是:移除在ys在出现过的元素后,xs剩下的元素。

minfree的复杂度是O(n^2),