算法: Divide and Conquer (Application of Quick Sort?!)

Question

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

You are the TA for a class with an enrollment of n students. You have their final scores (unsorted), and you must assign them one of the G available grades (A, B, C etc.). The constraints are (assuming n is a multiple of G):

• Exactly (n/G) students get each grade (for example, if n = 30, and G = {A,B,C}, then exactly 10 students get A, 10 get B, and 10 get C)
• A student with lower score doesn’t get a higher grade than a student with a higher score (however, they may get the same grade) Assuming that each student received a different score, derive an efficient algorithm and give its complexity in terms of n and G. Any algorithm that first sorts the scores will receive zero credit.

我的回答: 好吧，问题的最后一行表明，如果我尝试先对数组进行排序并将数组分成 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)，因为最小-最大问题的复杂度为 O(n)，而快速排序中的分区的复杂度为 O(n)。

请分享您的想法。

Answer 1

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