数组中第k大的数

方法：有两种。参见：http://hi.baidu.com/mianshiti/blog/item/3dc76cee353279dfb31cb1a0.html

第一种：使用排序（快速排序），将数组排序后，第k大的数就在第k个位置上。算法复杂度：o(n*logn)

第二种：类似快速排序的变种。通过二分的思想，找到第k大的数字，而不必对整个数组排序。

从数组中随机选一个数t，通过让这个数和其它数比较，我们可以将整个数组分成了两部分并且满足，{x, xx, ..., t} < {y, yy, ...}。
在将数组分成两个数组的过程中，我们还可以记录每个子数组的大小。这样我们就可以确定第k大的数字在哪个子数组中。
然后我们继续对包含第k大数字的子数组进行同样的划分，直到找到第k大的数字为止。
平均来说，由于每次划分都会使子数组缩小到原来1/2，所以整个过程的复杂度为O(N)。

 

public class FindKthMax {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] array=new int[]{2,4,3,4,7};
		int k=3;
		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]);
			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]);
			return ;
		}
		if(k<j)
			find(array,left,j-1,k);
		else
			find(array,j+1,right,k);
	}
	
}

运行结果：the 3th max number is:4