鸽巢原理及应用

文/一觉亮天

鸽巢原理经常用在判定存在性的问题。

鸽巢原理： n+1只鸽子往n个巢子里飞，则可以确定至少有一个巢里有大于等于二只鸽子。 m只鸽子往n个巢里飞， 则可以确定至少有一个巢里有大于等于ceiling(m/n)只鸽子。

下面举一个利用鸽巢原理解题的例子。

数轴上的一组无序实数，求出相邻两点间的最大间隙。要求算法的时间复杂度为n。

解此题最容易想到的就是先把这组实数排序，然后用一个循环遍历一遍排序后的序列，就可以找到相邻两点间的最大间隙。 但是我们知道，最快的排序算法的平均时间复杂度都是n*log(n)， 如快速排序和归并排序。 而如插入排序和冒泡排序等的时间复杂度为n的平方。所以这种办法是行不通的。

关于此题，我是一直没能想出时间复杂度为n的算法。 直到在书中找到了答案。算法的思路如下。

1. 找出这组数的最大值和最小值。 （时间复杂度为n）
2. 在最大值和最小值之间等间隔地构造n-1个桶，把除了最大值和最小值的n-2个数按照他们各自的值安排在相应的桶里。 每支桶里只需要记录属于这个桶的最大数和最小数。 （时间复杂度为n）
3. 根据鸽巢原理，有n-2个数，n-1个桶，则至少有一个桶是空的。 所以最大间隙只能存在于桶间和桶与最大值和最小值之间，不会出现在桶内。在最小值、各个桶和最大值之间遍历一遍，就可以求出最大间隙。 （时间复杂度为n）

下面是程序代码。

import scala._</p> <p>object Pigeon {<br /> def main(args:Array[String]){<br /> //read maximum number of real numbers.<br /> val num=readInt()</p> <p> //read num double number<br /> val points=new Array[Double](num)<br /> for (i<-0 until num){<br /> points(i)=readDouble()<br /> }</p> <p> //get the index of minimum & maximum<br /> val minIdx=min(points)<br /> val maxIdx=max(points)</p> <p> //initialize (num-1) bucket, maximum in 1 while minimum in 2 stands for empty bucket<br /> val bucket=new Array[(Double,Double)](num-1)<br /> for(i<-0 until num-1){<br /> bucket(i)=(points(maxIdx),points(minIdx))<br /> }</p> <p> //fill double numbers in bucket<br /> for(i<-0 until num){<br /> //not include maximum and minimum<br /> if(i!=minIdx && i!=maxIdx){<br /> var bucket_index =<br /> ((points(i)-points(minIdx))*(num-1)<br /> /(points(maxIdx)-points(minIdx))).toInt</p> <p> var minBucketVal=bucket(bucket_index)._1;<br /> var maxBucketVal=bucket(bucket_index)._2;<br /> if ( minBucketVal > points(i) ){<br /> minBucketVal = points(i)<br /> }<br /> if (maxBucketVal < points(i) ) {<br /> maxBucketVal = points (i)<br /> }<br /> bucket(bucket_index)=(minBucketVal,maxBucketVal)<br /> }<br /> }</p> <p> //iterate to get max_interval<br /> var max_interval:Double=0.0d;<br /> var previous_val:Double=points(minIdx)<br /> for(i<-0 until (num-1) ) {<br /> var (minBucketVal,maxBucketVal) = bucket(i)<br /> //it is not empty bucket<br /> if(minBucketVal<=maxBucketVal){<br /> var cur_interval=minBucketVal – previous_val<br /> if(cur_interval>max_interval) max_interval=cur_interval<br /> previous_val=maxBucketVal<br /> }<br /> }<br /> var cur_interval=points(maxIdx)-previous_val<br /> if(cur_interval>max_interval) max_interval=cur_interval</p> <p> //output the result<br /> println(max_interval.toString)<br /> }</p> <p> def min(ary:Array[Double]):Int={<br /> var idx:Int= 0;<br /> var i:Int=0;<br /> for(i<-0 until ary.length){<br /> if ( ary(i) < ary(idx) ){<br /> idx=i<br /> }<br /> }<br /> idx<br /> }</p> <p> def max(ary:Array[Double]):Int={<br /> var idx:Int= 0;<br /> var i:Int=0;<br /> for(i<-0 until ary.length){<br /> if ( ary(i) > ary(idx) ){<br /> idx=i<br /> }<br /> }<br /> idx<br /> }<br />}<br />

今天的文章鸽巢原理及应用分享到此就结束了，感谢您的阅读。