自学java编程练题1（ACM求众数）

nianxinzhuo233

问题描述：
给定含有n个元素的多重集合S，每个元素在S中出现的次数称为该元素的重数。多重集S中重数最大的元素称为众数。
例如，S={1，2，2，2，3，5}。多重集S的众数是2，其重数为3。
编程任务：
对于给定的由n 个自然数组成的多重集S，编程计算S 的众数及其重数。



输入：
第1行多重集S中元素个数n(n<=50000)；接下来的n 行中，每行有一个自然数。



输出：
输出文件有2 行，第1 行给出众数，第2 行是重数。(如果有多个众数，只输出最小的)


样例输入：
6
1
2
2
2
3
5



样例输出：
2
3


解题及思路：
方法一：

package acm;
import java.util.Scanner;

//众数问题
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();//输入自然数
        int arr[] = new int[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.nextInt();//赋值
        }
        /*
         * 思路：
         * 1.创建一个二维数组模拟map
         */
        mode1(arr);
    }

    //众数实现1
    public static void mode1(int[] arr){
        int length = arr.length;
        int newArr[][] = new int[length][2];
        //赋值
        for (int i = 0; i < newArr.length; i++) {

            boolean flag = true;
            for (int j = 0; j < i; j++) {
                if(newArr[j][0] == arr[i]){
                    newArr[j][1] = newArr[j][1]+1;
                    flag = false;
                }
            }
            if(flag){
                newArr[i][0] = arr[i];
                //newArr[i][1] == 0表示arr[i]中没有这个数，有这个数才保存到newArr里面
                newArr[i][1] = 1;
            }
        }
        int max = newArr[0][1];//用来存放众数，如3 2表示哦3这个数出现了2次，所以max=2
        int maxNumber = newArr[0][0];//用来存放是哪个数，如3 2表示哦3这个数出现了2次，所以maxNumber=3
        for (int i = 0; i < newArr.length; i++) {
            //这句话是查看输出的，newArr[i][1] == 0表示arr[i]中没有这个数，所以就不打印出来
//          if(newArr[i][1] != 0){
//              System.out.println(newArr[i][0]+":"+newArr[i][1]);
//          }
            if(max < newArr[i][1]){
                max = newArr[i][1];
                maxNumber = newArr[i][0];
            }

        }
        System.out.println(maxNumber+"\n"+max);
    }

方法二：

package acm;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

//众数问题
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();//输入自然数
int arr[] = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = in.nextInt();//赋值
}
/*

• 思路：

• 2.直接使用map
  */
  mode2(arr);
  }

  //众数实现2（map）
  public static void mode2(int[] arr){
  Map<Integer,Integer> map = new HashMap<Integer,Integer>();
  for (int i = 0; i < arr.length; i++) {
  if(!map.containsKey(arr[i])){
  //如果map中的键不包含有这个数，那么放入这个数的时候他的键的值就是1，即出现的次数为1
  map.put(arr[i], 1);
  }else{
  //如果map中的键包含有这个数，那么放入这个数的值的值加1，即出现的次数加1
  map.put(arr[i], map.get(arr[i])+1);
  }
  }
  int max = map.get(arr[0]);//得到最大的值的值，也就是出现的次数最大的值
  for (int m : map.values()) {
  //取出map中所有的值的值，遍历，得的到最大的值，也就是最大的出现次数
  if(max < m){
  max = m;
  }
  }
  for (int k : map.keySet()) {
  //取出map中所有的键的值，遍历，找出该键对应的值等于max的，也就是得到数
  if(map.get(k) == max){
  System.out.println(k);
  System.out.println(map.get(k));
  break;
  }
  }
  }
  }

第一次发解题贴，不喜勿喷，欢迎指导{:301_987:} {:301_987:} {:301_987:}

nianxinzhuo233

方法二代码的格式我没有设置成功，不好意思大家，希望大家看的懂

罗通晓

默默看着你 发表于 2021-11-25 14:46
目前社会主流py，建议学习python

真要找工作还得java，c++，go这些吧

vkery

我觉得没必要循环两次吧

[Java] 纯文本查看 复制代码

public static void cal(int[] arr) {
		Map<Integer, Integer> map = new HashMap<>();
		int num = 0;
		int maxCount = 0;
		for (int i = 0; i < arr.length; i++) {
			map.compute(arr[i], (integer, integer2) -> integer2 == null ? 1 : ++integer2);
			Integer count = map.get(arr[i]);
			if (i == 0) {
				num = arr[i];
				maxCount = 1;
			}
			if (count >= maxCount) {
				if (count == maxCount) {//重数相同
					if (arr[i] < num) {//取最小的众数
						num = arr[i];
					}
				} else {//更大的重数和对应的众数
					num = arr[i];
					maxCount = count;
				}
			}
		}
		System.out.println(num);
		System.out.println(maxCount);
	}

nianxinzhuo233

默默看着你 发表于 2021-11-25 14:46
目前社会主流py，建议学习python

做软件的话基本上都是java吧，人工智能大数据这些基本上是Python

nianxinzhuo233

vkery 发表于 2021-11-25 16:02
我觉得没必要循环两次吧
[mw_shl_code=java,true]public static void cal(int[] arr) {
                Map map = new ...

原谅我的菜，你这个我理解起来有点绕，不过还是谢谢你提出了你的想法，也是一种解题思路