3

这个问题是在 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。
  • Comparator 将比较结果中的 testScore，并为较高的分数返回 1，以便从高到低排序。
  • 遍历给定的结果列表并将所有测试结果放入映射中（检查条目是否存在，如果存在：添加到集合，如果不存在：使用新集合创建条目并将结果添加到列表中。
  • 遍历 HashMap，对于每个条目，我遍历前 5 个集合条目并获得平均值，然后将其放入另一个 HashMap，我最终将其返回。

现在这是我的问题：

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

PS 之前看到有人问过这个问题@计算平均值？但他不清楚，也没有提供骷髅。如果这违反了发布规则，我提前道歉。

4

2 回答 2

3

使用minHeap大小为 5 的 a。

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

于 2013-02-25T17:07:05.370 回答
1

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

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

于 2013-02-25T17:14:54.070 回答