加入收藏 | 设为首页 | 会员中心 | 我要投稿 上饶站长网 (https://www.0793zz.com.cn/)- 数据库平台、视觉智能、智能搜索、决策智能、迁移!
当前位置: 首页 > 大数据 > 正文

寻找第K大数的方法

发布时间:2021-03-09 05:29:39 所属栏目:大数据 来源:网络整理
导读:寻找一堆数中第K大的数,第一感觉是排序,然后将排序之后的值取第K个。但是实际上,这种方式最少的时间复杂度是O(nlogn)。有更简单的方式可以实现线性的时间复杂度。 算法总是有穷尽的,而思想无穷尽,而实用算法的本质是用空间去换取时间。 这里的方案是:


寻找一堆数中第K大的数,第一感觉是排序,然后将排序之后的值取第K个。但是实际上,这种方式最少的时间复杂度是O(nlogn)。有更简单的方式可以实现线性的时间复杂度。


算法总是有穷尽的,而思想无穷尽,而实用算法的本质是用空间去换取时间。


这里的方案是:

1)假设所有的数都是正数,并且事先知道最大数的范围

2)开辟一个数组numArr,长度至少要为最大数加一,初始化数组中每个元素都为0

3)对于某个数T,在对应的数组 numArr[T] 的位置上加一(将所有的数都进行当前操作)

4)从数组的最顶端开始向下累加,sum+=numArr[i],当sum的值大于等于K时,当前的i即为这组数中第K大的值


如下图示:


寻找第K大数的方法


寻找第K大数的方法



在这个例子中,当我们取第5大的数的时候,从顶部向下累加,发现加到第三个数的时候,sum就为5了,所以此时第5大的数应该就是对应的i值为7.



给段代码:

/**
 * 寻找第K大大数值
 * @author blyang
 */
public class KBig {

	public static void main(String[] args) {
		
		int K = 5;
		int[] nums = new int[]{ 0,3,2,7,8,9,4,6,1,7};
		int max = 10;
		int[] numArr = new int[max];
		int sum = 0;
		
		for( int i=0; i<numArr.length; i++ ){
			numArr[i] = 0;
		}
		
		for(int num : nums){
			numArr[num]++;
		}
		
		int i=0;
		for( i=numArr.length-1; i>=0; i--){
			sum += numArr[i];
			if(sum >= K){
				break;
			}
		}
		
		System.out.println(i);
	}
}

(编辑:上饶站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读