文/一觉亮天
鸽巢原理经常用在判定存在性的问题。
鸽巢原理： n+1只鸽子往n个巢子里飞，则可以确定至少有一个巢里有大于等于二只鸽子。
m只鸽子往n个巢里飞，
则可以确定至少有一个巢里有大于等于ceiling(m/n)只鸽子。
下面举一个利用鸽巢原理解题的例子。
数轴上的一组无序实数，求出相邻两点间的最大间隙。要求算法的时间复杂度为n。
解此题最容易想到的就是先把这组实数排序，然后用一个循环遍历一遍排序后的序列，就可以找到相邻两点间的最大间隙。
但是我们知道，最快的排序算法的平均时间复杂度都是n*log(n)，
如快速排序和归并排序。 而如插入排序和冒泡排序等的时间复杂度为n的平方。所以这种办法是行不通的。
关于此题，我是一直没能想出时间复杂度为n的算法。
直到在书中找到了答案。算法的思路如下。
- 找出这组数的最大值和最小值。
（时间复杂度为n）
- 在最大值和最小值之间等间隔地构造n-1个桶，把除了最大值和最小值的n-2个数按照他们各自的值安排在相应的桶里。
每支桶里只需要记录属于这个桶的最大数和最小数。
（时间复杂度为n）
- 根据鸽巢原理，有n-2个数，n-1个桶，则至少有一个桶是空的。
所以最大间隙只能存在于桶间和桶与最大值和最小值之间，不会出现在桶内。在最小值、各个桶和最大值之间遍历一遍，就可以求出最大间隙。
（时间复杂度为n）
下面是程序代码。