首页 文章

第三大区域没有分拣

提问于
浏览 次
3

我正在进行编程的入门课程，并试图找到一个圆圈阵列中的第三大区域，然后返回可以找到这个圆圈的索引而不进行排序，但遇到了一些麻烦 .

输入

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;
}
c++ arrays

3 回答

  • 3

    这些初始化不正确：

    Circle largest = *arr[0];
Circle secondlargest = *arr[size - 1];
Circle thirdlargest = secondlargest;

    它们假设一些通常不正确的条件：第一个元素大于最后一个元素（在测试用例中为true，一般为false），并且有一个额外的元素等于最后一个元素（非常不合理） .

    您应该将 largest ， secondlargest 和 thirdlargest 初始化为前3个元素，正确排序：

    largest_idx = 0;
secondlargest_idx = 1;
thirdlargest_idx = 2;

// bubble-sort of an array of 3 elements:
// swap 0 <-> 1 if needed
// swap 1 <-> 2 if needed
// swap 0 <-> 1 if needed
if (arr[largest_idx]->getArea() < arr[secondlargest_idx]->getArea())
    std::swap(largest_idx, secondlargest_idx);
if (arr[secondlargest_idx]->getArea() < arr[thirdlargest_idx]->getArea())
    std::swap(secondlargest_idx, thirdlargest_idx);
if (arr[largest_idx]->getArea() < arr[secondlargest_idx]->getArea())
    std::swap(largest_idx, secondlargest_idx);

    这里我使用索引而不是对象，因为你的函数必须计算索引，而不是返回对象 .

    然后开始检查第四个元素（第一个尚未检查的元素）：

    for (int i = 3; i < size; i++) {
    ...
}

    检查对象两次是不正确的，例如，第二大元素，重复两次，可以让你忘记第三大元素 .

    回复于
  • 0

    首先，您应该在代码中的三个位置替换< . 例如，这里： if (largest.getArea() > arr[i]->getArea()) 如果第i个元素的面积大于当前最大面积，则应输入 if 块 . 此外，您应该记住第一个，第二个和第三个圆圈索引而不是圆圈本身 . 您始终使用 i 的值更新 index ，但它仅在最后一个 else 块中正确 . 如果您记住索引而不是圆圈，则会返回 thirdLargestIdx .

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

    只是为了完整性，有O（n）算法用于在数组中找到第k个最大元素：https://en.wikipedia.org/wiki/Median_of_medians

    回复于
  • 1

    请更喜欢标准容器而不是传统的C阵列和指针算术 . 在合理的情况下也尝试使用标准算法 .

    auto getThirdLargestArea(const std::vector<Circle>& circles) -> int {
  // this will hold the three largest circles known
  auto largest = std::vector<std::pair<int, const Circle*>>{};

  // iterate over all circles
  for(size_t i = 0; i < circles.size(); ++i) {
    // add the current index and circle to the largest list
    largest.insert(std::find_if(std::begin(largest), std::end(largest),
                                [&](const std::pair<int, const Circle*>& c) {
                                  return c.second->getArea() < circles[i].getArea();
                                },
                   std::pair<int, const Circle*>{i, &(circles[i])});
    // we are only interested in the three largest, so drop the rest.
    largest.resize(std::min(largest.size(), 3));
  }

  if(largest.size() < 3)
    // there were less than 3 circles -> signal an error
    return -1;

  // now we can simply read the third largest from your vector
  return largest[2].first;
}

    我使用指针来防止复制圆圈 . 由于 largest 从不拥有圈子，因此此代码中的任何地方都没有泄漏 . 由于 largest 中的指针始终指向const向量 circles ，因此指针不能在任何地方悬挂 .

    注意：此答案中的代码需要C 11功能，未经测试 . 因此它可能包含一些错误 .

    回复于

相关问题