2

任何有关如何解决以下问题的帮助将不胜感激。我也发布了一些关于这个问题的想法。

你是一个有 n 名学生的班级的助教。您有他们的最终分数（未排序），您必须为他们分配 G 可用等级之一（A、B、C 等）。约束是（假设 n 是 G 的倍数）：

  • 恰好 (n/G) 名学生获得每个成绩（例如，如果 n = 30，并且 G = {A,B,C}，则正好 10 名学生获得 A，10 名学生获得 B，10 名学生获得 C）
  • 分数较低的学生不会比分数较高的学生获得更高的分数（但是，他们可能会得到相同的分数）假设每个学生获得不同的分数，推导出一个有效的算法并给出其复杂度G. 任何首先对分数进行排序的算法都将获得零分。

我的回答：好的，问题的最后一行说，如果我尝试先对数组进行排序并将数组分成 G 等份，我就不好了。当使用最佳排序算法时，这将花费 O(n log n)。所以，我想到了一个复杂的解决方案。我认为这个问题是快速排序可以派上用场的一个例子，因为我们不需要对属于同一年级的学生进行排序，我们可以有 k 个关键元素，并且关键元素都是等距的。但是，我们没有得到学生的分数，我们也被告知每个学生都有不同的分数。

首先，我使用 MaxMin Divide and Conquer Algorithm 计算最大和最小分数，这将花费 O(n) 时间。使用最大值和最小值，我们可以通过计算粗略地找到每个等级的关键要素。(Max-Min)/k = 最低等级，2*(Max-Min)/k = 第二最低等级。k-1*(Max-Min)/k = 最高等级。

现在使用这些作为关键元素，我们可以只执行快速排序的分区方法，第一次需要 n 时间，第二次需要 n-(Max-Min)/k 等等。因此算法的时间复杂度为 O(n)，因为 min-max 问题的复杂度为 O(n)，而快速排序中的 Partition 的复杂度为 O(n)。

请分享你的想法。

4

2 回答 2

1

这基本上是一个选择问题，只是你一次做 G 个选择。

http://en.wikipedia.org/wiki/Quickselect算法的修改应该在这里工作。虽然 Quicksort 总是递归地下降到两个分区并且原始 Quickselect 只下降到包含第 k 个索引的那个，但是这个问题的算法应该下降到一个分区当且仅当它包含n/G, 2*n/G, ...(G-1)*n/G数组索引之一 -那些是成绩之间的分裂点。

这些索引是等级之间的分割点，所以你最终得到一个数组，其中分割点之间的元素不一定排序，但点之间的块是。

于 2015-02-08T20:41:44.613 回答
1

您可以将所有分数放入（最大）优先级队列中，然后从中提取 n/G 组。这仍然是一种隐式排序，但仍然没有被规则禁止。

于 2015-02-08T20:27:52.840 回答