c++ - 没有排序的第三大区域

Question

我正在上一门编程入门类(class)，我试图在圆数组中找到第三大区域，然后返回可以在不排序的情况下找到该圆的位置的索引，但遇到了一些麻烦。

输入

Circle [0] 157/50
Circle [1] 314/25
Circle [2] 1413/50 
Circle [3] 1256/25 
Circle [4] 152/7

预期输出

2

实际输出

4

如果我错了请纠正我，但我认为我为 largest、secondlargest 和 thirdlargest 分配了错误的值？为什么返回 4？这是我到目前为止所拥有的，感谢您的帮助。 ^_^

int getThirdLargestArea(Circle** arr, int size) {
    Circle largest = *arr[0];
    Circle secondlargest = *arr[size - 1];
    Circle thirdlargest = secondlargest;

    int index = 0;

    for (int i = 1; i < size; i++) {
        if (largest.getArea() > arr[i]->getArea()) {
            thirdlargest = secondlargest;
            secondlargest = largest;
            largest = *arr[i];
            index = i;
        }

        else if (secondlargest.getArea() > arr[i]->getArea()) {
            thirdlargest = secondlargest;
            secondlargest = *arr[i];
            index = i;

        }

        else if (thirdlargest.getArea() > arr[i]->getArea()) {
            thirdlargest = *arr[i];
            index = i;
        }
    }

    return index;
}

Answer 1

首先，您应该在代码中的三个位置将> 替换为<。例如，这里:if (largest.getArea() > arr[i]->getArea()) 如果第 i 个元素的面积大于你目前最大的区域。此外，您应该记住第一个、第二个和第三个圆圈索引，而不是圆圈本身。你总是用 i 的值更新 index 但它只在最后一个 else block 中是正确的。如果您记得索引而不是圆圈，您将返回 thirdLargestIdx。

您还应该注意最大、第二大和第三大变量的初始值。您不应该假设您选择的圆圈大小的任何特定顺序。

为了完整起见，有一个 O(n) 算法用于查找数组中的第 k 个最大元素:https://en.wikipedia.org/wiki/Median_of_medians