在线性时间复杂度内求解第k小元素问题

给定n个元素，要求解其中第k小的元素，一般采用先排序后然后直接得结果的过程。在数据量小的情况下没问题，时间复杂度是O(n*logn). 但是当数据量非常大的时候就要考虑是否有更好的算法来代替全局排序。

这里，采用剪枝策略，即如果要在线性时间内得到问题的解，必须在每次迭代的过程中用O(n)的时间剪去部分元素，使得在下次迭代过程中不参与比较。

 

《算法设计与分析导论》一书给出了一个比较经典的线性时间复杂度下的求解算法。

 

核心思想：

我们以每5个元素为子集划分源数组，然后对每个子集排序求出中位数，这样的中位数集合组成一个新的序列M，对M递归的求解其中位数p，得到的p即为划分点。p将源数组划分为3部分：
  * s1：所有小于p的元素
  * s2: 所有等于p的元素
  * s3: 所有大于p的元素

下一轮迭代的时候根据输入的level参数判断该剪去哪部分元素，具体参见代码实现部分。

 

 这样，每一轮迭代至少剪去n/4的元素（画个中位数排列的图出来就容易看出），则最坏情况下的时间复杂度表示为：

 T(n)=T(3n/4)+T(n/5)+O(n)

 

其中

  * T(3n/4)是下一轮迭代的最大数据量情况下的时间复杂度
  * T(n/5)是求寻找中位数组成集合的中位数的时间复杂度
  * 
根据递推公式可以求得该算法的时间复杂度是O(n)

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ElementsHandler {
	
	/**
	 * 找出浮点型数组array的第level小元素
	 * 核心思想：如果要在线性时间内得到问题的解，必须在每次迭代的过程中用O(n)的时间剪去部分元素，使得在下次迭代过程中不参与比较
	 * 我们以每5个元素为子集划分源数组，然后对每个子集排序求出中位数，这样的中位数集合组成一个新的序列M，对M递归的求解其中位数p，得到的p
	 * 即为划分点。p将源数组划分为3部分：
	 * s1：所有小于p的元素
	 * s2: 所有等于p的元素
	 * s3: 所有大于p的元素
	 * 
	 * 下一轮迭代的时候根据输入的level参数判断该剪去哪部分元素，具体参见代码实现部分。
	 * 
	 * 这样，每一轮迭代至少剪去n/4的元素，则最坏情况下的时间复杂度表示为：
	 * T(n)=T(3n/4)+T(n/5)+O(n)--其中T(3n/4)是下一轮迭代的最大数据量情况下的时间复杂度，
	 * T(n/5)是求寻找中位数组成集合的中位数的时间复杂度
	 * 
	 * 可以求得
	 * 找出浮点型数组array的第level小元素的算法时间复杂度是O(n)
	 * @param level
	 * @param array
	 * @return
	 */
	public static double calcValueLevel(int level, Double[] array)
	{
		if(array==null||level<=0||level>array.length)
			throw new IllegalArgumentException("Wrong input!");
		
		int len=array.length;
		if(len==1)
			return array[0];
		
		int blockSize=5;//以每5个元素为子集划分源数组
		int blocks=len%blockSize==0?len/blockSize:len/blockSize+1;
		
		List<Double> midList=new ArrayList<Double>();
		for(int i=0;i<blocks;i++)
		{
			int start=i*blockSize;
			int end=sortBlock(array, start, blockSize);
			midList.add(array[start+(end-start-1)/2]);//添加各个5元素且排好序组的中位数(偶数个的情况取第N/2个数，注意这里不存在偶数情况，因为以5个元素为单位划分)
		}
		
		Double[] midsArray=null;
		midsArray=midList.toArray(new Double[midList.size()]);//获得每5个元素组中的中位数组成的数组
		
		double mmidValue=calcValueLevel((midList.size()+1)/2,midsArray);//递归求解[n/5]组数的中位数组成的集合的中位数
		
		List<Double> l_list=new ArrayList<Double>();
		List<Double> e_list=new ArrayList<Double>();
		List<Double> h_list=new ArrayList<Double>();
		
		for(int i1=0;i1<len;i1++)
		{
			if(array[i1]<mmidValue)
			{
				l_list.add(array[i1]);
			}
			else
			{
				if(array[i1]>mmidValue)
					h_list.add(array[i1]);
				else
					e_list.add(array[i1]);
			}
		}
		
		if(level<=l_list.size())
		{
			Double[] lArray=null;
			lArray=l_list.toArray(new Double[midList.size()]);
			
			return calcValueLevel(level,lArray);
		}
		else
		{
			if(l_list.size()+e_list.size()>=level)
			{
				return mmidValue;
			}
			else
			{
				Double[] hArray=null;
				hArray=h_list.toArray(new Double[h_list.size()]);
				
				return calcValueLevel(level-l_list.size()-e_list.size(),hArray);
			}
		}		
	}

	/**
	 * 在blockSize比较小的情况下，这里针对5个单位排序，任意方法都可以，我选择简单的选择排序算法
	 * @param array
	 * @param start
	 * @param blockSize
	 */
	public static int sortBlock(Double[] array, int start, int blockSize) {
		int end=(start+blockSize)>array.length?array.length:start+blockSize;
		//选择排序:小->大
		for(int i=start;i<end-1;i++)
		{
			for(int j=i+1;j<end;j++)
			{
				if(array[i]>array[j])
				{
					double temp=array[i];
					array[i]=array[j];
					array[j]=temp;
				}
			}
		}
		return end;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int level=10;
		Double[] d=new Double[]{2.1,1.2,3.1,1.2,2.1,7.3,4.8,5.3,5.2,2.1,10.0,0.1,-1.1};	
		double res=ElementsHandler.calcValueLevel(level,d);
		System.out.println("第"+level+"小的数是："+res);
		
		Arrays.sort(d);
		
		System.out.println(Arrays.toString(d));
	}

}