在未排序的向量中查找第K个最小元素（迭代式）

我正在尝试创建一个返回向量中第k个最小元素的代码。例如：例如：假设您有一个向量rand，其中包含元素{0,3,2,5} 并且用户输入2作为K的值。函数应该从向量返回元素2，因为它是向量中的第2个（第k个）最小元素。在未排序的向量中查找第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; 
     } 

      } 
    } 

}

它不断将一些庞大的数字，是不是即使在载体中。

来源

2013-10-17 Manny O

+10

的，除非你真的需要* *不这样做（例如，这是家庭作业）使用'的std :: nth_element'。 –

实际上排序向量并从前面返回第k个元素可能是一个更快的方法，除非你真的想要迭代求解 – smac89

是的，我必须用未排序的向量来执行 –

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); 
}

来源

2013-10-17 23:46:14 LihO

我正在使用i

这是一个迭代解决方案。他不需要从0开始，因为他可以根据前k项最小的假设开始。他只是忘了创建第k个项目的列表。他需要这个来比较和存储找到的最小的k个项目。 – JustinDanielson

@MannyO：看我的编辑（在行下）。 – LihO

这里是我的解决方案的一些不完整的代码。它只需要传递一个向量。这将以vec的线性时间运行。希望它清除一切。我以前的文章有点罗嗦。尽管如此，我仍然把它放在这个源码下面

int iterative_kth_element(vector<int>& vec, size_t k) 
{ 
    int mins[k]; 
    //assume first k elements are min 
    for(int i=0; i<k; i++) 
    { 
     mins[i] = vec[i]; 
    } 

    //TODO: 
    //sort mins array here 
    //bubble sort is okay if k is small, or pivot 

    for(int i=k; i < vec.size(); i++) 
    { 
     //since mins is sorted, mins[k-1] is the highest value 
     if(vec[i] < mins[k-1]) 
     { 
      mins[k-1] = vec[i]; 
     } 

     //TODO: 
     //sort mins array here 
     //you could do a slick bubble sort starting from 
     //the back of mins until you find the location 
     //for the new min item 
    } 

    return mins[k-1]; 
}

//在前文

如果你正在寻找第k最小的项目。你应该用第一个k项来初始化一个数组。或者将索引存储到找到最小项目的vec中（将从0,1,2,3开始，...，K）

int index = 0; 
int min = vec[0];

应该

int* mins = new int[k]; 
for(int i=0; i < k; i++) { 
    mins[i] = vec[i]; 
}

我也建议保持此数组排序ķ最小的整数。如果您知道最大物品的位置，您只需检查vec中的每个元素与最大物品的分钟数。不过，您需要一种排序方法，每次找到比分钟小的东西时就会调用它。

经过一次vec迭代后，您应该在该数组中有最小的k个项目。只需返回最大的项目。存储在阵列中的位置0或k-1处。

还有其他值得注意的地方：如果k大于vec.size（）/ 2，你应该寻找（vec.size（）-k）最大的项目。

这应该是log（k * n）时间，最大内存占用为1.5n（k是vec.size（）/ 2是最差情况）。

其中n是vec的大小，k是函数中的parm（如果实现该注释，则k的上限为n/2）。

最糟糕的情况是获取数字的降序顺序列表，其中k是n的一半大小。

来源

2013-10-18 00:01:51 JustinDanielson

你在这段代码中遗漏了一些东西，加上这个是C++而不是c – smac89

好的调用，忘了把malloc转换成int *。我只是将它更改为新的int [k]。 – JustinDanielson

所以用这种方法我不需要第二个循环？或者我会不得不调整它？ –

1 /你有一个载体，但你几乎只使用它作为数组

2 /考虑使用的迭代器。

3 /您正在接受作为参考的向量，这意味着对它的修改（如擦除元素）在方法范围之外有效，您确实想要这么做吗？

来源

2013-10-18 00:12:16 vincentB

从这里开始：http://en.wikipedia.org/wiki/Selection_algorithm

int iterative_kth_element(vector<int>& vec, size_t k) 
{ 
    int minIndex, minValue; 
    for (int i = 0; i < k; i++) 
    { 
     minIndex = i; 
     minValue = vec[i]; 
     for (int j = i+1; j < n; j++) 
     { 
      if (vec[j] < minValue) 
      { 
       minIndex = j; 
       minValue = vec[j]; 
      } 
     } 
     int tmp = vec[i]; 
     vec[i] = vec[minIndex]; 
     vec[minIndex] = tmp; 
    } 
    return vec[k]; 
}

来源

2013-10-18 00:14:04

整数的阵列设置。

从数组中删除所有正元件，其最大和最小元件之间分配。
计算数组的负单元之和。
要计算最小素元

来源

2014-01-07 21:01:12 user3127168

在未排序的向量中查找第K个最小元素（迭代式）

回答

相关问题