c++ - 数组中的最大 X 值

Question

我正在尝试编写一个函数，该函数采用数组、大小和数组中 X 个最大成绩的数量。
例如:

array = { 90,45,77,43,67,88 }, maxGrades = 3

结果应该是:

retArray = {90,77,88} or {90,88,77}

我尝试过的:

int * GetMaxGrades(int * grades, int size, int maxGrades)
{
     int *retArray;

     if (maxGrades > size)
        return grades;

     retArray = (int*)calloc(sizeof(int) * maxGrades);

     for (int i = 0; i < size; i++)
     {
         for (int j = 0; j < maxGrades; j++)
            if (grades[i] > retArray[j])
            {
                 retArray[j] = grades[i];
                 break;
            }
     }

     return retArray;
}

但我复活了 {90,88,67}

编辑 如果我像那样更改内部循环:

        if (grades[i] > retArray[j])
        {
            if (j + 1 < maxGrades)
                retArray[j + 1] = retArray[j];

            retArray[j] = grades[i];
            break;
        }

它解决了部分问题，但这是最好的方法吗？

Answer 1

虽然可以使用选择算法在线性时间内完成，但通常使用存储前 k 个元素的最小堆来完成，在每次迭代时 - 您检查堆中的最小元素是否大于您正在迭代的当前版本，如果是，则替换它们。

这是 O(nlogk) 的时间，只有 O(k) 的额外内存，并且只需要对数据进行一次遍历(所以如果你的元素正在流中)。

以下代码是 C++11(具有优雅的 for-each 循环)，但使用相同的数据结构很容易将其转换为旧的 c++ 代码。

#include <iostream>
#include <vector>
#include <queue>

int main(void) {
    int array[] = { 90,45,77,43,67,88 }; 
    int maxGrades = 3;
    std::priority_queue<int, std::vector<int>, std::greater<int>> q;
    for (int x : array) { 
        // populate first maxGrades elements
        if (q.size() < maxGrades) {
            q.push(x);
        // replace if new element is higher than smallest in heap.
        } else if (q.top() < x) {
            q.pop();
            q.push(x);
        }
    }
    // print elements
    std::cout << "elements: ";
    while (!q.empty()) { 
        std::cout << q.top() << " ";
        q.pop();
    }
    return 0;
}