在一列数中求第k大的数目字
在一列数中求第k大的数字
面试官的意图 根本不是让你用Array。sort()啊
这个题目的一种思路是利用快排思想来解决,可以达到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; } }
1 楼
albrich
2012-02-29
你是怎么想出来的,太厉害了,我有点看不懂
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.
望改进!!!
类似这样的数组:这是好多重复的数放在一起,你这个方法就不太好使了,你可以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.
望改进!!!
3 楼
albrich
2012-02-29
你可以看看我写的方法:http://hi.baidu.com/albrich/blog/item/012483da9518c22a33fa1c12.html
4 楼
502220545
2012-04-07
albrich 写道
你可以看看我写的方法:http://hi.baidu.com/albrich/blog/item/012483da9518c22a33fa1c12.html
面试官的意图 根本不是让你用Array。sort()啊