数组中前k大的数

问题：《编程之美》page139.寻找最大的k个数。

 

方法一：通过全排序(快速排序)，然后获取前k个数即位最大的k个数。算法复杂度：O(nlogn).

方法二：通过部分排序。（选择排序，冒泡排序），直接获取前k个最大的数。算法复杂度O(n*k).当k比较小的时候可以考虑

方法三：快速排序的变种。前面寻找数组中第k大数的过程中，当找准数组中第k大数的位置时，数组中比k大的数据都在k的left边，比k小的数据都在k的right边。从而获取前k大的数据。其实也是部分排序。算法复杂度:O(n).

 

 

public class FindKth {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array=new int[]{2,4,3,4,7};
		int k=4;
		find(array,0,array.length-1,k-1);
		
	}

	public static void find(int[] array,int left, int right,int k){
		if(k==left && k==right) {
			System.out.println("the "+(k+1)+"th max number is:" + array[k]);
			print(array,k);
			return ;
		}
		
		int i=left;
		int j=right+1;
		int key=array[left];
		
		while(true){
			do{
				i++;
			}while(i<=right&&array[i]>key);
			
			do{
				j--;
			}while(j>=left&&array[j]<key);
			if(j<i) break;
			int tmp=array[i];
			array[i]=array[j];
			array[j]=tmp;

		}
		int tmp=array[left];
		array[left]=array[j];
		array[j]=tmp;
		if(j==k) {
			System.out.println("the "+(k+1)+"th max number is:" + array[j]);
			print(array,k);
			return ;
		}
		if(k<j)
			find(array,left,j-1,k);
		else
			find(array,j+1,right,k);
	}
	
	public static void print(int[] array,int k){
		System.out.println("find numbers are: ");
		for(int i=0;i<=k;i++){
			System.out.print(array[i]+ " ");
		}
	}
	
}

 

运行结果：

 the 4th max number is:3

 find numbers are: 

 7 4 4 3 

方法四：如果N很大，比如100亿。可以采用一个数组，数组中始终保持访问过的所有的数中的前k个最大的数据，每次从k个数中淘汰掉最小的数，到最后可以一次遍历获取前k个最大的数据。通过维持一个容量为k的最小堆的方式来实现。算法复杂度O(n*log2k)