java - Amazon.com 学生最终成绩

Question

这个问题出现在 Amazon.com 面试的在线测试中。确切的问题是:

Given a list of test results (each with a test date, Student ID, and the student’s Score), return the Final Score for each student. A student’s Final Score is calculated as the average of his/her 5 highest test scores. You can assume each student has at least 5 test scores.

Use the following skeleton for your solutions

class TestResult{
   int studentId;
   Date testDate;
   int testScore;
}

public Map<Integer, Double> getFinalScores(List<TestResult> resultList){
   return null;
}

我的解决方案是这样的:

• 我创建了一个 HashMap<Integer, SortedSet<TestResult>称为 studentIdToResultSet。
• Comparator 将比较结果中的 testScore，并为较高的分数返回 1，以便从高到低排序。
• 遍历给定的结果列表并将所有测试结果放入映射中(检查条目是否存在，如果存在:添加到集合中，如果不存在:使用新集合创建条目并将结果添加到列表中。
• 遍历 HashMap，对于每个条目，我遍历前 5 个集合条目并获取平均值，将其放入另一个 HashMap，最终返回。

现在这是我的问题:

1. 我不知道我的解决方案的复杂性 (O) 是多少。我最好的猜测是它是 O(n+n)，但我不确定。
2. 这个问题是否有更优的解决方案？
3. 如果我向问题添加一个约束条件，即返回的 map 必须按照学生排名的顺序进行迭代，会怎样？

附言之前看到有人问过这个问题@Calculating the average?但他很不清楚，也没有提供骨架。如有违反发帖规则，敬请见谅。

Answer 1

使用大小为 5 的 minHeap。

复杂度:O(klogn)，k =5 ==> O(logn)。和 O(n+m) ，通常 = O(max(n,m) 。在你的情况下它是 O(n)。