二维数组，使用 HashMap 的最佳平均计算器

Question

问题陈述：我有一个包含学生姓名和相应标记的二维字符串数组，如下所示

String[][] scores = {{"Bob","85"},{"Mark","100"},{"Charles","63"},{"Mark","34"}};

我想计算所有可用学生的最佳平均分，即根据上述输入，最佳平均分应该是 85。

我的尝试： 我尝试使用 HashMap 解决这个问题，如下所示。

public int  bestAverageCalculator(String[][] scores) {

    // This HashMap maps student name to their list of scores
    Map<String,List<Integer>> scoreMap = new HashMap<String,List<Integer>>();
    for(String[] score:scores) {
        String name = score[0];
        int currentScore =Integer.parseInt(score[1]);

        if(scoreMap.containsKey(name)) {
            List<Integer> scoreList = scoreMap.get(name);
            scoreList.add(currentScore);
            scoreMap.put(name, scoreList);
        }
        else {
            List<Integer> scoreList = new ArrayList<Integer>();
            scoreList.add(currentScore);
            scoreMap.put(name, scoreList);
        }
    }
    //scoreMap will be {Charles=[63], Bob=[85], Mark=[100, 34]}
    //After Map is formed i am iterating though all the values and finding the best average as below
    int bestAverage = 0;
    for(List<Integer> value:scoreMap.values()) {
        int sum = 0;
        int count = 0;
        for(int i:value) {
            sum+=i;
            count++;
        }
        int average = (int)Math.floor(sum/count);
        if(average>bestAverage)
            bestAverage = average;
    }

    return bestAverage;// returns 85

}

实施是正确的，我得到了预期的答案，但我被告知 space 程序的复杂性更高，并且可以在不使用 List<Integer> 作为标记的情况下实现，我无法理解如何在不存储标记列表的情况下即时计算平均值。

请提出除了HashMap之外是否还有其他方法可以解决此问题。

如有任何帮助，我们将不胜感激。

Answer 1

您可以为每个学生存储固定数量的数据：

学生姓名
所有学生的总分
学生的分数

这将使 space 复杂度 O(m) 其中 m 是唯一学生的数量（而不是你的 O(n) 其中 n 是数量的标记）。

例如，您可以拥有一个具有这 3 个属性的 Student class（并将数据存储在 List<Student> 中），或者您可以拥有一个 Map<String,int[]>键是学生的名字，值是包含分数总和和分数数的两个元素的数组。

您可以在遍历输入时构建此数据。

现在您可以计算每个学生的平均值并找到最高平均值。

Answer 2

好吧，为了 space 节省，您可以每人存储两个号码 avgSum 和 count 最后计算平均值。

Answer 3

我已经根据您的代码使用 Map<String,int[]> 和

实现了@Eran 的方法

key: 学生姓名

值：两个元素的数组[the sum of the scores, the number of scores]

public int  bestAverageCalculator(String[][] scores) {

    // This HashMap maps student name to their total scores and count in an int array format of [totalScores, count]
    Map<String,int[]> scoreMap = new HashMap<String,int[]>();
    for(String[] score:scores) {
        String name = score[0];
        int currentScore =Integer.parseInt(score[1]);

        if(scoreMap.containsKey(name)) {
            int[] scoreCount = scoreMap.get(name);
            scoreCount[0] += currentScore;
            scoreCount[1] ++;
            scoreMap.put(name, scoreCount);
        }
        else {
            int[] scoreCount = new int[]{currentScore, 1};
            scoreMap.put(name, scoreCount);
        }
    }

    int bestAverage = 0;
    for(int[] value:scoreMap.values()) {
        int average = (int)Math.floor(value[0]/value[1]);
        if(average>bestAverage)
            bestAverage = average;
    }

    return bestAverage;// returns 85

}

Answer 4

@Eran 的想法，但有了 Student class，至少对我来说更清晰了

import java.util.*;

public class Main {
    static String[][] scores = {{"Bob", "85"}, {"Mark", "100"}, {"Charles", "63"}, {"Mark", "34"}};

    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        for (String[] score : scores) {
            String name = score[0];
            int currentScore = Integer.parseInt(score[1]);

            Student student = findStudentByName(name, students);
            if (student != null) {
                student.setNumberOfScores(student.getNumberOfScores() + 1);
                student.setSumOfScores(student.getSumOfScores() + currentScore);
            } else {
                student = new Student(name, 1, currentScore);
                students.add(student);
            }
        }
        findStudentWithBestAverage(students);
    }

    private static void findStudentWithBestAverage(List<Student> students) {
        Student bestStudent = null;
        int bestAverage = 0;
        for (int i = 0; i < students.size(); i++) {
            if ((students.get(i).getSumOfScores() / students.get(i).getNumberOfScores()) > bestAverage) {
                bestStudent = students.get(i);
                bestAverage = (students.get(i).getSumOfScores() / students.get(i).getNumberOfScores());
            }
        }
        System.out.println(bestStudent + " with average: " + bestAverage);
    }

    private static Student findStudentByName(String name, List<Student> students) {
        for (int i = 0; i < students.size(); i++) {
            if (students.get(i).getName().equals(name)) {
                return students.get(i);
            }
        }
        return null;
    }

    public static class Student {
        private String name;
        private int numberOfScores;
        private int sumOfScores;

        public Student(String name, int numberOfScores, int sumOfScores) {
            this.name = name;
            this.numberOfScores = numberOfScores;
            this.sumOfScores = sumOfScores;
        }

        public String getName() {
            return name;
        }

        public int getNumberOfScores() {
            return numberOfScores;
        }

        public void setNumberOfScores(int numberOfScores) {
            this.numberOfScores = numberOfScores;
        }

        public int getSumOfScores() {
            return sumOfScores;
        }

        public void setSumOfScores(int sumOfScores) {
            this.sumOfScores = sumOfScores;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return name.equals(student.name);
        }

        @Override
        public int hashCode() {
            return Objects.hash(name);
        }

        @Override
        public String toString() {
            return "Student{" +
                    "name='" + name + '\'' +
                    ", numberOfScores=" + numberOfScores +
                    ", sumOfScores=" + sumOfScores +
                    '}';
        }
    }
}

二维数组，使用 HashMap 的最佳平均计算器

2D Array, best average calculator using HashMap

java

algorithm

collections

space-complexity