我正在尝试编写一个返回 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 中的巨大数字。
最佳答案
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);
}
关于c++ - 查找未排序 vector 中的第 K 个最小元素(迭代),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19439137/