当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2012-12-27   作者:128kj   来源:转载   浏览:
摘要: 题目大意:   输入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 3
题目大意:
  输入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);  
    }  
  }
}  



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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
此题有2种变形: 1、不能修改node结构,要求时间O(N). 2、可以修改node结构,要求时间O(logN). 这里
第三章三续、求数组中给定下标区间内的第K小(大)元素 作者:July、上善若水、编程艺术室。 出处:
第三章三续、求数组中给定下标区间内的第K小(大)元素 作者:July、上善若水、编程艺术室。 出处:
文章转载:http://blog.csdn.net/v_july_v/article/details/6452100 第三章三续、求数组中给定下标
快速排序 和归并排序一样,也是采用分治(Divide and Conquer)思想。分为三步: 分解:将数组A[p...q
建立一个K个数字的大顶堆,然后逐步插入数据和最后的哪个数字进行比较,如果大就插入堆中,否则就Pa
#include<iostream> using namespace std; /* | 参数说明:输入数组in[], 输出数组out[], 输
转自: http://blog.csdn.net/pi9nc/article/details/12220851 1)算法简介 计数排序(Counting sort
(1) 问题描述 最短路径问题是图论中的一个经典问题,主要研究成果有Dijkstra、Floyd等优秀算法,Dij
选择问题——在序列中按顺序找到某个元素。这可以用排序方法做到,即先排个序,在找到指定元素,但
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号