2

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

            }
    }

}

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

4

5 回答 5

1

Start here: 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-18T00:14:04.537 回答
1 
for(int i = k;i<vec.size();i--)

似乎不对，假设k是 always < vec.size()，那么 conditioni<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-17T23:46:14.040 回答
0

这是我的解决方案的一些不完整代码。它只需要通过向量 1 次。这将在相对于 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];
}

我还建议对这个由 k 个最小整数组成的数组进行排序。如果您知道最大的项目在哪里，您只需将 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 是函数中的参数。（如果您实现该注释，则 k 的上限为 n/2）。

最坏的情况是得到一个按降序排列的数字列表，其中 k 是 n 的一半。

于 2013-10-18T00:01:51.763 回答
0

设置整数数组。

  1. 从数组中删除分配在最大和最小元素之间的所有正元素。

  2. 计算数组负单元格的总和。

  3. 计算素元素的最小值

于 2014-01-07T21:01:12.767 回答
0

1/ you have a vector but you almost use it only as an array

2/ consider using an iterator.

3/ you are receiving the vector as a reference, which means modifications on it such as erasing an element is effective out of the scope of the method, do you really want to do that?

于 2013-10-18T00:12:16.003 回答