在一列数中求第k大的数字

这个题目的一种思路是利用快排思想来解决，可以达到O（nlogn）的时间效率。

详细代码如下：

/*
 * 在一列数中寻找第k大的数，使用快排思想，一趟快排后会返回一个基准点的位置，如果该位置loc正好处于
 * 要求的第k个数的位置，则该位置的数即为所求；如果loc>k，说明要求的第k大的数，在左边子数组中，如果loc<k，
 * 则要求的数为右边子数组的第k-loc个位置的数
 */
public class Findnth {
	public static void main(String args[]){
		int array[] = {5, 6, 7, 9, 8, 4, 3, 2, 1, 10, 12, 11, 13, 14, 15, 16, 17, 19, 18, 20} ;
		int re=select(array,0,array.length-1,15);
		System.out.println("第---小的数是："+re);
	}
	
	public static int select(int a[],int left,int right,int k){//求第k小的数
		if(left==right){
			return a[left];
		}
		int loc=partition(a,left,right);//返回一趟快排后某个基准点的位置
		int kth=loc-left+1;//该基准数在当前的子数组中是第几小的数
		if(k==kth){//如果该趟排序后返回的基准位置所处的位置正好是这个子数组的第k小的数
			return a[loc];//返回处于该位置的值就是要求的第k小的数
		}else if(k<kth){
			return select(a,left,loc-1,k);//求左边子数组中的第k小的数
		}else{
			return select(a,loc+1,right,k-kth);//求右边子数组中的第k-kth小的数
		}
	}
	public static int partition(int a[],int left,int right){
		//一趟快排，返回以a[left]为基准点的位置
		int temp=a[left];
		while(left<right){
			while(left<right&&a[right]>=temp){
				right--;
			}
			a[left]=a[right];
			while(left<right && a[left]<=temp){
				left++;
			}
			a[right]=a[left];
		}
		a[left]=temp;
		return left;
	}
}

 

评论

4 楼 502220545 2012-04-07  

albrich 写道

你可以看看我写的方法：http://hi.baidu.com/albrich/blog/item/012483da9518c22a33fa1c12.html

面试官的意图 根本不是让你用Array。sort（）啊

3 楼 albrich 2012-02-29  

你可以看看我写的方法：http://hi.baidu.com/albrich/blog/item/012483da9518c22a33fa1c12.html

2 楼 albrich 2012-02-29  

我又仔细看了一下这个方法不太对，int [] n={1,23,12,12,12,58,24,44,32,56,56,56,67,23,44};
类似这样的数组：这是好多重复的数放在一起，你这个方法就不太好使了，你可以int re=select(array,0,array.length-1,4);
System.out.println("第4小的数是："+re);
int re=select(array,0,array.length-1,3);
System.out.println("第3小的数是："+re);
正确的答案应该是第3小的数是23，第4小的数是24，按你这方法都是12.



望改进！！！

1 楼 albrich 2012-02-29  

你是怎么想出来的，太厉害了，我有点看不懂