方法:有两种。参见: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
分享到:
相关推荐
给定一数组,查找数组中第k大的数。代码中借助快速排序中的partition方法来实现。
在编程中非常常用的算法:计算整形数组中第k小的数
主要介绍了Python实现查找数组中任意第k大的数字算法,涉及Python针对数组的排序、查找等相关操作技巧,需要的朋友可以参考下
17082 两个有序数序列中找第k小(必做) 时间限制:1000MS 内存限制:65535K 提交次数:0 通过次数:0 题型: 编程题 语言: C++;C;VC;JAVA Description 已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为...
本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法。分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数。这里数组可以是有重复的值! 下面是自己写的...
典型的Top K算法 找出一个数组里面前K个最大数.doc
c语言面试题 c语言面试题之双指针数组中的K-diff数对
js代码-数组中的第K个最大元素
具体思路为:第一次先遍历数组找到最大的数,第二次遍历从剩下的数组中找到最大的数(在整个数组中第二大的数)…共需遍历k次,这种方法的时间复杂度为O(N*k) 方法三:综合法 该方法思路是: (1)维护一个大小为k的...
已知两个已经排好序(非减序)的序列X和Y,其中X的长度为m,Y长度为n, 现在请你用分治算法,找出X和Y的第k小的数,算法时间复杂度为O(max{logm, logn})。
求数组中第K大的数可以基于快排序思想,步骤如下:1、随机选择一个支点2、将比支点大的数,放到数组左边;将比支点小的数放到数组右边;将支点放到中间(属于左部分)3、设左部分的长度为L,当K < L> L时,递归地在有...
问题:有一个大小为n的数组A[0,1,2,…,n-1],求其中第k大的数。该问题是一个经典的问题,在《算法导论》中被作为单独的一节提出,而且其解决方法很好的利用了分治的思想,将时间复杂度控制在了O(n),这多少出乎我们...
首先将向量V从中间位置分开,分成左和右,分好后,中间值的索引如果恰恰等于K,就找到了,否则如果中间元素索引大于K,则在左子表中继续查找,忽略右子表,如果中间值索引小于K,则在右子表中继续查找,如此循环往复...
在主函数中输入10个整数到数组中,调用函数move()完成将数组元素循环移动k位(要求函数参数为:1数组名;2数组元素个数;3循环移动的位数k)。当k>0时,实现循环右移;当k时,实现循环左移。循环右移一位的意义是:将...
示例2:输入:[1, 2, 3, 4, 5], k = 1输出: 4解释: 数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和
J, K两种类型热电偶的分度表数组,浮点型数组。H头文件。方便用于工程计算和相关编程应用。每一度一个浮点数,K型热电偶的数组范围从-60度到+1370度;J型热电偶的温度范围:-210度到+1200度。
易语言随机打乱数组源码,随机打乱数组
数与数组加减:k+/-A %k加或减A的每个元素 数组乘数组: A.*B %对应元素相乘 数组乘方: A.^k %A的每个元素k次方;k.^A,分别以k为底A的各元素为指数求幂值 数除以数组: k./A和A./k %k分别被A的元素除 数组除法: ...