c++ - 在未排序的 vector 中查找第 K 个最小元素(迭代)

Question

我正在尝试编写一个返回 vector 中第 k 个最小元素的代码。例如:假设您有一个 vector rand，其中包含元素 {0, 3, 2, 5}用户输入 2 作为 K 的值。然后该函数应返回 vector 中的元素 2，因为它是 vector 中第二(第 k)个最小元素。

到目前为止，这是我的代码:

int iterative_kth_element(vector<int>& vec, size_t k)
{
    int index = 0;
    int min = vec[0];


    for(int i = k;i<vec.size();i--) {
            for (int j = 1; j < vec.size();j++) {
            if ( min > vec[j] ) {
                min = vec[j];
                index = i;
            }
        vec.erase(vec.begin() + index);

        if (i == 1) {
            return min;
        }

            }
    }

}

它不断返回一些甚至不在 vector 中的巨大数字。

Answer 1

for(int i = k;i<vec.size();i--)

似乎不对，假设 k总是 < vec.size() , 然后条件 i<vec.size()在这里完全没用。相反，您可能更愿意添加:

for(int i = k; i > 0; i--)

嵌套循环实际上应该检查所有元素，因此它应该从 0 开始(它跳过第一个元素):

for (int j = 0; j < vec.size(); j++) {
             ^

我相信

index = i;

本来是:

index = j;

并确保所有可能的执行路径都返回一些值，注意编译器给你的警告。再放一张return函数末尾的语句:

return min;

---

但是您的主要问题是:

• 你应该更新min在嵌套循环开始执行之前
• 嵌套循环的范围不应包含 erase打电话

尝试:

int foo(std::vector<int>& vec, const size_t k)
{
    int index = 0;
    int min = -1;

    for(size_t i = 0; i < k; ++i) {
        if (vec.empty()) return min;
        min = vec[0];
        for (size_t j = 0; j < vec.size(); ++j) {
            if (vec[j] < min) {
                min = vec[j];
                index = j;
            }
        }
        vec.erase(vec.begin() + index);
    }
    return min;
}

int main() {
    int a[] = {0, 3, 2, 5};
    std::vector<int> v(a, a+4);
    std::cout << foo(v, 2);
}