技术凡人

Appearance

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

概述 ​

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

题目 ​

问题描述 ​

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

输入格式 ​

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

输出格式 ​

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

样例输入 ​

bash
6
10 1 10 20 30 20
6
10 1 10 20 30 20

样例输出 ​

10

解题思路 ​

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

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

代码如下：

java
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);
    }
}
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

java
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;
    }
}
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循环来解决迭代的问题

java
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;
    }
}
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;
    }
}