CSP认证 201312-1:出现次数最多的数


CSP认证2013年12月第一题:出现次数最多的数

概述

这学期老师要求每个人必须考一个CCF CSP认证考试,并且将会将认证的20%的成绩作为期末成绩,这下必须好好准备了就从简单的开始准备吧,毕竟我是求稳的人,先稳定了简单题再提高是个不错的选择。

题目

问题描述

  给定n个正整数,找出它们中出现次数最多的数。如果这样的数有多个,请输出其中最小的一个。

输入格式

  输入的第一行只有一个正整数n(1 ≤ n ≤ 1000),表示数字的个数。
  输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。

输出格式

  输出这n个次数中出现次数最多的数。如果这样的数有多个,输出其中最小的一个。

样例输入

6
10 1 10 20 30 20

样例输出

10

解题思路

先找到最大出现次数,然后将保存的每个key中找到最小的跟最大出现次数对应的值就好了

思路一:直接用时间换空间,通过一个大数组来索引所有值的数量

代码如下:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        //每个元素代表数出现的数量
        int[] numbers = new int[10001];
        Scanner sc = new Scanner(System.in);
        int numberCount = sc.nextInt();
        for (int i=0;i<numberCount;i++){
            numbers[sc.nextInt()]++;
        }
        int max=0,index=0;
        for (int j=0;j<10001;j++){
            if (numbers[j]>max){
                max=numbers[j];
                index=j;
            }
        }

        System.out.println(index);
    }
}

基本思路:找出最大值之后就记录下最大值的位置索引,然后打印索引就是数目最大的值,并且由于从小到大排列,最后的值就是按顺序出现的最小的index

思路二:使用hash记录每个数字出现的次数—-迭代器

这里思路很清晰,就是找到最大值之后从hash表中找出对应的key并且给key排序找到最小key

public class Main {
    public static void main(String[] args) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        Scanner scanner = new Scanner(System.in);
        int numberCount = scanner.nextInt();
        int countNew = 0;
        Integer tempNumber;
        int max=0;
        for (int i=0;i<numberCount;i++){
            tempNumber = scanner.nextInt();
            countNew = hashMap.get(tempNumber)==null ? 1:hashMap.get(tempNumber)+1;
            if (countNew>max){
                max=countNew;
            }
            hashMap.put(tempNumber,countNew);
        }
        ArrayList<Integer> al = (ArrayList<Integer>) getKeys(hashMap,max);
        Collections.sort(al);
        System.out.println(al.get(0));
    }

    public static Object getKeys(Map map,Object value){
        ArrayList<Object> res=new ArrayList<>();
        Set<Map.Entry<Object,Object>> mapSet = map.entrySet();
        Iterator<Map.Entry<Object,Object>> iterator = mapSet.iterator();
        while(iterator.hasNext()){
            Map.Entry<Object,Object> objectObjectEntry = iterator.next();
            if (objectObjectEntry.getValue().equals(value)){
                res.add(objectObjectEntry.getKey());
            }
        }
        return res;
    }
}

思路三:使用hash记录每个数字出现的次数—-遍历keyset

这里和上面不同的是这里使用的是for循环来解决迭代的问题

import java.util.*;

public class Main {
    public static void main(String[] args) {
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        Scanner scanner = new Scanner(System.in);
        int numberCount = scanner.nextInt();
        int countNew = 0;
        Integer tempNumber;
        int max=0;
        for (int i=0;i<numberCount;i++){
            tempNumber = scanner.nextInt();
            countNew = hashMap.get(tempNumber)==null ? 1:hashMap.get(tempNumber)+1;
            if (countNew>max){
                max=countNew;
            }
            hashMap.put(tempNumber,countNew);
        }
        ArrayList<Integer> al = (ArrayList<Integer>) getKeys(hashMap, max);
        Collections.sort(al);
        System.out.println(al.get(0));
    }

    public static Object getKeys(Map map, Object value){
        Set<Object> keySet=map.keySet();
        ArrayList<Object> result = new ArrayList<>();

        for (Object key:keySet){
            if (map.get(key).equals(value)){
                result.add(key);
            }
        }
        return result;
    }
}

文章作者: Cyber-Peng
版权声明: 本博客所有文章除特別声明外,均采用 CC BY-ND 4.0 许可协议。转载请注明来源 Cyber-Peng !
 上一篇
win10 开始菜单图标显示不正常,如何恢复 win10 开始菜单图标显示不正常,如何恢复
前情提要今天笔记本硬盘掉线了,电脑蓝屏。当下吓得要死,好在只是硬盘线松开了加固了之后又满血复活了,但是开始菜单的图标都消失了变成了下面的样子: 当时没有截图大概每一个都像上面这个一样,变成了默认的程序图标,我先后找了几个解决方案实验最终解
2020-02-24
下一篇 
关于博客内容创作和博客部署技术结构的思考 关于博客内容创作和博客部署技术结构的思考
前一段时间将自己的博客转移到了hexo上面,之前的博客是Jpress搭建的,Jpress还是有一定的好处就比如可以开发一些插件来增加各种功能,甚至自动运营公众号,不过缺点也很明显由于博客内容保存在数据库中,而图片保存在一个附件文件夹里面,这
2020-02-20
  目录