来源:编程之美2.5
题目:寻找N个数中最大的k个数
书中提供的解法很多,有些用java实现起来还真有点难度,很帖两个解法吧,都是比较简单的,复杂的后面再补上。
//求N个数中最大的k个数
import java.util.PriorityQueue;
public class KMax2_5 {
private long []n;
private int maxNum = 100;
private int k = 5;
private final static int BOUND = 1000;
//生成测试数组
private void generateNumbers() {
n = new long[maxNum];
for(int i = 0; i < maxNum; i++) {
n[i] = Math.round(Math.random() * BOUND);
System.out.println(n[i]);
}
}
//解法一,利用JDK里的PriorityQueue队列,该队列会从小到大排列数据
//这种方式应该和自己建一个大小为k的数组,然后排好序,再插入排序的方式差不多。
private void selectKmax1() {
PriorityQueue pq = new PriorityQueue(k);
for(int i = 0; i < k; i++) { //前k个数入队
pq.offer(n[i]);
}
for(int i = k; i < maxNum; i++) {
if(n[i] > (Long)pq.peek()) { //有大的就往里填数据
pq.poll();
pq.offer(n[i]);
}
}
System.out.println("-----------PriorityQueue------------");
while(pq.size() > 0) {
System.out.print((Long)pq.poll()+" ");
}
System.out.println();
}
//解法二,选择排序,排前k个即可,当k 不是很大时效率应该不错
private void selectMax2(){
int index;
long temp;
for(int i=0;i<k;i++){//只需要循环k次即可
index=i;
for(int j=i+1;j<n.length;j++){
if(n[j]>n[index])index=j;
}
if(index!=i){//说明需要交换
temp=n[i];
n[i]=n[index];
n[index]=temp;
}
}
System.out.println("------选择排序结果--------");
for(int i=0;i<k;i++)System.out.print(n[i]+" ");
System.out.println();
}
public static void main(String[] args) {
KMax2_5 kmax = new KMax2_5();
kmax.generateNumbers();//产生maxNum个随机整数
kmax.selectKmax1();//
kmax.selectMax2();
System.out.println("Complete!");
}
}
分享到:
相关推荐
### 寻找最大的K个数的关键知识点解析 #### 一、问题背景与基本思路 在IT面试场景中,“寻找最大的K个数”是一个常见的算法题目。该问题要求从大量无序数字中找到最大的K个数。这个问题看似简单,但实际上包含了多...
用最优的算法,寻找到一个序列之中的K各最大的数
文档通过之前的寻找最小k个数的问题作为铺垫,探讨了Top K算法的实现,特别是寻找最大k个数的情况。文章强调,虽然寻找最大k个数和最小k个数在原理上相似,但Top K算法在搜索引擎和大数据处理等领域有更广泛的应用。...
### 微软技术面试经典题目解析:寻找最大的K个数 #### 领域背景 在软件工程和技术面试领域,特别是在像微软这样的大型科技公司,面试官常常会提出一些算法和数据结构方面的问题来评估候选人的技术水平。这些面试题...
在Java编程中,寻找最大的K个数是一个常见的算法问题,主要出现在面试和数据结构与算法的练习中。这个问题要求从一个整数数组中找到最大的K个元素,而不仅仅是最大值。传统的解法通常包括排序整个数组,然后取前K个...
如果第k个元素比最大值小,更新最大值。接着,跳过k个元素,再比较第2k个元素,依此类推。直到遍历完整个数组,最后的最大值即为第k小元素。跳跃选择的平均时间复杂度为O(n),最坏情况下为O(n^2)。 4. 分治法: 将...
在Python编程中,高效地找出一个集合中最大的K个数或者最小的K个数是一个常见的需求。Python标准库提供了一个名为`heapq`的模块,它包含了一系列与堆相关的功能,能够有效地解决这类问题。本篇文章将详细讲解如何...
在这个问题中,我们要在数组中找到第k个最小的元素,同时考虑到数组中可能存在重复的元素。这个问题在实际应用中广泛出现,比如数据库查询优化、数据分析以及在线竞赛编程等场景。 在Visual C++环境下实现寻找第k小...
为了统计数组中每个数出现的次数,可以使用计数器数组的方式。首先创建一个长度为10001的数组(考虑到元素的最大值为10000),然后遍历输入数组,对于每个元素,在对应的计数器数组位置上加1。最后再遍历一次计数器...
文章进一步对h(k)进行定义,即h(k)为前k个自然数之和。通过这个函数的定义,作者建立了一个关于k的不等式关系,以此来界定n的范围。 文章也提到了一个关键的函数P(k),这个函数利用了h(k)和h(k+1)来界定n的范围,这...
K-means算法的核心思想是通过迭代寻找数据的最佳划分,将数据集分为K个簇(cluster),每个簇的中心(centroid)由簇内所有数据点的均值计算得出。这个过程不断重复,直到簇的分配不再发生变化或者达到预设的迭代...
在计算机科学和编程领域,"通过最大堆求topk"是一种高效的算法,常用于寻找一个大数组中的前k个最大元素。这个算法的核心是利用数据结构——最大堆(Max Heap)来实现。最大堆是一种完全二叉树,其中每个父节点的值...
k优解通常出现在排序、选择问题或竞赛排名等场景,例如找到前k个最大或最小的元素。 描述虽然没有提供具体细节,但可以推测是关于如何有效地在一组数据中找出第k个最佳解的不同方法。 标签"ui"可能是指这些方法...
// 寻找满足整除3,并且末尾是0或者5的最大数 for (int i = len; i >= 1; i--) { if (a[i].rest == 0 || a[i].rest == 2) { cout [i].x; } } return; } ``` 算法复杂性分析: 该算法的时间复杂度主要体现在...
今天,我们将探讨一种高效的解决方案,该方案在C语言中实现,并采用经典的埃拉托斯特尼筛法(Sieve of Eratosthenes)来寻找并打印出指定范围内的最大k个素数。 埃拉托斯特尼筛法,这个名字来源于古希腊数学家...
- **功能**:通过交换数组中某些元素的位置来提高寻找最大值和最小值的效率。 - **实现**: - 首先计算中间索引 `k`。 - 将数组分为两部分,对于每一对 `(x[i], x[k+i])`,如果 `x[k+i] [i]`,则交换它们的位置。 ...
在一组无序的数值中,第k大的数字是指除去其中最大的k-1个数字后剩下的那个最大值。例如,对于数组[3, 5, 6, 7, 2, -1, 9, 3],第5大的数字是6,因为它在去除数组中的前4个最大元素(9, 7, 6, 5)后剩余的最大值。 ...
### Python求n以内最大的k个素数 #### 素数的基本概念与重要性 素数是只能被1和它本身整除的大于1的自然数。素数的研究历史源远流长,从古希腊时期的欧几里得到现代数学家们的研究,素数一直是数学领域的一个核心...
然后,依次弹出堆顶元素(即当前最大元素),并记录已弹出的元素个数。当弹出的元素个数等于k-1时,堆顶剩下的元素就是第k小的元素。堆排序法的时间复杂度为O(n log n)。 3. **线性时间复杂度的解决方案**: 当...