`
128kj
  • 浏览: 601244 次
  • 来自: ...
社区版块
存档分类
最新评论

POJ2092:计数排序,求第K大的元素

阅读更多
题目大意:
  输入N和M,N就是N次测试,M是说每次测试产生的数据个数,数据范围在1-10000之间。现要求统计输出N次测试中数据出现次数第二多的所有数。当输入0,0时结束。

样例:
4 5
20 33 25 32 99
32 86 99 25 10
20 99 10 33 86
19 33 74 99 32
3 6
2 34 67 36 79 93
100 38 21 76 91 85
32 23 85 31 88 1
0 0
Sample Output

32 33
1 2 21 23 31 32 34 36 38 67 76 79 88 91 93 100

分析:先统计,然后排序(用Arrays.sort()就可以了),注意输出的时候要按 play 的 num 的升序输出。

AC代码:
import java.util.Scanner;
import java.util.Arrays;
 class play  implements Comparable {  
    int num;  //N次测试中出现的数字
    int s;  //此数字在N次测试中出现的次数

   public int compareTo(Object o) {   
     play b=(play)o; 
     if(this.s==b.s)  //s相等,按num升序
        return this.num-b.num;  
    else  
        return b.s-this.s;  //按s从大到小降序排
  }
  
    public String toString(){
      return "["+num+","+s+"]";
    }
 }

 public class Main{
  public static void main(String args[]){  
    int n,m;  
    Scanner in=new Scanner(System.in);
    while(true){  
        n=in.nextInt();
        m=in.nextInt();
        play p[]=new play[10001]; //数据范围在1-10000,数据i用play[i]来记录相关信息
        for(int i=0;i<10001;i++)
             p[i]=new play();
        int temp;  
        if(n==0 && m==0)  
            break;  
        for(int i=0;i<n;i++)  
            for(int j=0;j<m;j++)  
            {  
               temp=in.nextInt();//测试中出现的数字
               
               p[temp].num=temp;//记录这个数字
                p[temp].s++;  //记录此数字出现的次数
            }  
        Arrays.sort(p);  //将p按s降序排序
     
         int i=1;  
     
        while(p[i].s==p[i+1].s)  //从下标1开始输出所有出现次数第二多的数字
        {  
            System.out.printf("%d ",p[i].num);  
            i++;  
        }  
             
        System.out.printf("%d\n",p[i].num);  
    }  
  }
}  



0
4
分享到:
评论

相关推荐

    经典 的POJ 分类

    根据给定的信息,我们可以将这些知识点分为几个大类别:数据结构、图论、搜索算法、动态规划、数学问题以及字符串处理等。 ### 数据结构 #### 队列 - **题目示例**: - POJ 3295:考察队列的基本应用。 #### ...

    acm新手训练方案新手必备

    - POJ 1753: 排序相关问题 - POJ 2965: 排序应用实例 - **搜索**:包括深度优先搜索(DFS)、广度优先搜索(BFS)等。 - **示例题目**: - POJ 1328: DFS的应用 - POJ 2109: BFS的应用 - POJ 2586: 搜索技巧展示 -...

    acm训练计划(poj的题)

    - (POJ3252, poj1850, poj1019, poj1942):解决计数问题时的一种方法。 4. **概率与期望**: - (poj2635, poj3292, poj1845, poj2115):概率论的基本概念及期望值的计算。 5. **博弈论**: - (poj3273, poj3258...

    直接插入排序练习:POJ 2388

    1. 从第二个元素开始,将其视为待插入的元素。 2. 比较待插入元素与前面已排序的元素,如果待插入元素较小,则将已排序元素逐个后移,直到找到合适的位置插入。 3. 重复步骤2,直到所有元素都插入到正确的位置,完成...

    大顶堆应用:POJ2010

    大顶堆是一种特殊的完全二叉树,其每个节点的值都大于或等于其子节点的值,常用于实现优先队列,快速找到最大元素,或者进行高效的排序算法,如堆排序。 在编程竞赛中,大顶堆经常被用来解决时间复杂度要求较高的...

    POJ1-7试题

    这是西北工业大学的POJ试题的答案,欢迎下载!

    poj题目分类

    3. 多边型的简单算法(求面积)和相关判定(点在多边型内,多边型是否相交):例如 poj1408、poj1584。 4. 凸包:例如 poj2187、poj1113。 这些知识点涵盖了算法、数据结构、数学、计算几何学等领域的多个方面,为...

    ACM北大训练

    - poj2388: 涉及排序问题,可用快速排序或归并排序解决。 ##### 3. 并查集 - **定义**: 并查集是一种支持并运算和查询运算的数据结构。 - **应用场景**: 常用于处理不相交集合的合并及查询问题。 - **示例题目**: ...

    POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类

    - **解释**:排列组合问题通常涉及从n个不同元素中选取k个元素的所有可能的方式。 #### 3. 概率统计 - **例题**:poj3273, poj3258, poj1905, poj3122 - **解释**:概率统计问题通常涉及计算某个事件发生的概率。 ...

    POJ2586-Y2K Accounting Bug

    【标题】"POJ2586-Y2K Accounting Bug" 是一道来自北京大学在线判题系统POJ(Problem Set)的编程题目。该题目主要关注的是计算机编程中的一个历史问题——Y2K千年虫问题(Year 2000 Problem),同时也涉及到会计...

    大(小)顶堆练习:POJ 1442

    大顶堆通常用于快速找到当前最大元素,例如在求解最大值问题或执行堆排序时。小顶堆则用于维护最小元素,例如在实现最小堆或进行堆调整时。这两种数据结构在处理动态集合并需要高效查询最大或最小元素的场景下非常...

    堆排序练习:POJ 2388

    通过不断调整堆,将最大元素(大顶堆)或最小元素(小顶堆)移动到堆顶并移除,可以实现排序。 在POJ 2388这个特定问题中,我们可能需要处理的数据特性、输入输出格式以及时间空间限制等信息,通常会在题目描述中给...

    极角排序:POJ 1696(叉积+深搜)

    标题中的“极角排序”是一种特殊的排序算法,主要用于解决特定问题,例如在平面上的点集按照极角顺序排列。这种排序方式对于处理图形问题,尤其是计算几何领域的问题非常有用。在POJ 1696这个编程题目中,很可能需要...

    西工大poj习题

    【标题】:“西工大poj习题” 这个标题指的是来自西安工业大学(Xi'an Jiaotong University,简称“西工大”)的POJ(Problem Oriented Judgment)在线编程练习平台上的习题集合。POJ是一个面向大学生的在线编程...

    西北工业大学poj

    【标题】"西北工业大学poj" 是一个与编程竞赛相关的资源集合,主要针对的是Programming Online Judge(POJ)平台上的题目。POJ是中国最早的在线编程训练网站之一,它提供了大量的编程题目供用户练习,旨在提升程序员...

    POJ算法题目分类

    * 递归和分治法:递归和分治法是指将问题分解成多个小问题,通过解决小问题来解决大问题,如 poj3295。 * 递推:递推是指通过前一个结果来计算当前结果的方法,如 poj1068、poj2632、poj1573、poj2993、poj2996。 * ...

    西工大c语言poj答案

    【标题】"西工大c语言poj答案"所涉及的知识点主要集中在C语言编程以及算法的实践应用上。POJ(Programming Online Judge)是西北工业大学提供的一种在线编程评测系统,它为学习者提供了大量的编程题目,以检验和提升...

    poj1094 拓扑排序

    题目“poj1094”即是要求我们实现一个拓扑排序的解决方案。 **拓扑排序**的基本思想是:对于有向无环图G,如果存在一条从顶点u到顶点v的路径,那么在拓扑排序结果中,u一定出现在v之前。拓扑排序可以得到多个不同的...

Global site tag (gtag.js) - Google Analytics