Amazon.com学生期末成绩

Question

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

给出一个测试结果列表(每个都有测试日期、学生ID和学生分数)，返回每个学生的最终分数。学生的期末成绩是根据他/她5个最高考试分数的平均值计算出来的。你可以假设每个学生至少有5个考试成绩。 在解决方案中使用以下框架

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

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

我的解决办法是这样：

• 我创建了一个名为HashMap<Integer, SortedSet<TestResult>的studentIdToResultSet。
• 比较器将比较结果中的testScore，并返回1以获得较高的分数，从而将其排序为最高到最低。
• 迭代给定的结果列表，并将所有测试结果放到映射中(检查是否存在条目，如果有，请检查: add to set，if no :用新集创建条目，并将结果添加到列表中。
• 在HashMap上迭代，对于我在前5个集合条目上迭代的每个条目，得到平均值，将其放入另一个HashMap中，并最终返回。

下面是我的问题：

1. 我不知道我的解决方案的复杂性(O)是什么。我最好的猜测是它是O(n+n)，但我不确定。
2. 这个问题有更好的解决方案吗？
3. 如果我在问题中添加了一个约束，即返回的地图必须按照学生排名的顺序迭代，该怎么办？

我看到有人在@ Calculating the average?之前问过这个问题，但他很不清楚，也没有提供骨架。如果这违反了发帖规则，我提前表示歉意。

Answer 1

使用大小为5的minHeap。

复杂度: O(klogn)，k =5 ==> O(logn)。和O(n+m)，一般= O(max(n，m) )。在你的例子中，它是O(n)。

Answer 2

您的算法似乎具有O(nLog (n))时间复杂度。你的树可以有任何大小，包括最坏的情况下的n。不用使用树，您可以在每个学生id中使用最小堆。每次添加第六项后，删除最小值，使其始终保持最佳的5分。

就像Droider解释的那样，这样可以保证线性时间在n中。