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

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分类POJ分类POJ分类POJ分类POJ分类POJ分类

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

    poj经典数据结构题目解题报告

    通过遍历数组,找到最小的两个非零元素进行合并,然后更新对应的计数。然而,当数据范围非常大时,如本题中的20000个数字,每个数字最大为50000,数组大小将达到1亿,无法直接内存分配。 在第三种尝试中,开发者...

    ACM算法总结--最新总结的ACM算法

    4. **Polya计数**(如poj1286, poj2409, poj3270, poj1026):利用群论方法解决计数问题,适用于化学结构分析、图案设计等领域。 #### 几何算法 1. **几何计算**:涉及点、线、面的操作,如距离计算、交点判断、...

    线段树题目

    在构建线段树时,需要考虑如何根据第一个元素移动到最后一个元素时逆序数的变化规律来进行更新。 - **POJ 2828** 和 **POJ 2180**:这两道题都需要从后往前推进,线段树用于存储空位数量,以便快速查找空位的位置。...

    ACM程序设计大赛,推荐图书和推荐网站

    - **问题描述**: 给定一个数字串和一个删除次数k,求出经过k次删除后可能获得的最大数字。 - **5.4 背包问题** - **0-1背包问题**: 只能选择每个物品一次,求解最大价值。 - **可拆背包问题**: 物品可以分割,...

Global site tag (gtag.js) - Google Analytics