查找第K最小的元素在未排序的载体（迭代） [英] Finding the Kth Smallest Element in an unsorted vector (Iteratively)

问题描述

我试图做一个code，它返回一个矢量的第k个最小元素。 例如： 比方说你有一个载体兰特其中包含的元素{0，3，2，5} 而用户输入2作为K赋值 该函数应该然后返回元件2从载体，因为它是第2次（第k）最小的元素在载体

I'm trying to make a code that returns the kth smallest element in a vector. For example: Lets say you have a vector rand which contains elements {0, 3, 2, 5} And the user inputs 2 as a value for K. The function should then return element 2 from the vector since it is the 2nd (kth) smallest element in the vector.

到目前为止，这是我的code：

so far this is my code:

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

            }
    }

}

它保持返回一些巨大的数字，是不是即使在载体中。

it keeps returning some huge number that is not even in the vector.

推荐答案

从这里开始：的http：// EN .wikipedia.org /维基/ 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];
}

这篇关于查找第K最小的元素在未排序的载体（迭代）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！