探求第K大数的要领

探求一堆数中第K大的数，第一感受是排序，然后将排序之后的值取第K个。可是现实上，这种方法起码的时刻伟大度是O(nlogn)。有更简朴的方法可以实现线性的时刻伟大度。

算法老是有穷尽的，而头脑无限尽，而适用算法的本质是用空间去调换时刻。

这里的方案是：

1）假设全部的数都是正数，而且事先知道最大数的范畴

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

3）对付某个数T，在对应的数组 numArr[T] 的位置上加一（将全部的数都举办当前操纵）

4）从数组的最顶端开始向下累加，sum+=numArr[i]，当sum的值大于便是K时，当前的i即为这组数中第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);
	}
}

（编辑：湖南网）

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