7

How to find indexes of 5 the biggest elements in vector ? For example std::vector<int> how to find indexes of 5 biggest values but not to change original vector ?

4

5 回答 5

13

std::partial_sort( v.begin(), v.begin()+5, v.end() )以某种方式对向量进行排序，即 5 个最小值被排序并且位于v. 其余的未排序。

由于您需要索引并保留原始索引：
用 0..n-1 中的数字填充一个新向量并提供一个比较函数，v[a] > v[b]而不是a > b：

struct Comp{
    Comp( const vector<int>& v ) : _v(v) {}
    bool operator ()(int a, int b) { return _v[a] > _v[b]; }
    const vector<int>& _v;
}

vector<int> vx;
vx.resize(v.size());
for( int i= 0; i<v.size(); ++i ) vx[i]= i;
partial_sort( vx.begin(), vx.begin()+5, vx.end(), Comp(v) );

vx[0..4]包含索引。

于 2012-09-18T11:41:20.917 回答
1

您可以从原始向量制作副本，并使用 STL 中的专用算法对其进行部分排序nth_element：

bool cmp (int i,int j) { return (i<j); }    
int main () {
      vector<int> myvector;
      vector<int>::iterator it;

      // set some values:
      for (int i=1; i<10; i++) myvector.push_back(i);   // 1 2 3 4 5 6 7 8 9

      random_shuffle (myvector.begin(), myvector.end());

      // using default comparison (operator <):
      std::vector<int> copy_of_orig = myvector;
      nth_element (copy_of_orig.begin(), copy_of_orig.begin()+5, copy_of_orig.end(), cmp);
      // Display the first five biggest elts.
      for (int i = 0; i < 5; ++i)
        std::cout << copy_of_orig[i] << std::endl;
}
于 2012-09-17T20:27:26.770 回答
1

1个解决方案：

解决方案是 O(n)，其中 n 是正在检查的向量中的元素数。

创建一个长度为 5 的向量迭代器的出队，初始化为 NULL 读取正在检查的向量的元素并 push_back 索引{想法是根据读取的新元素数据是否小于将新索引推到前面或后面后索引的数据或大于前索引的数据，如果出队中的数据已经为NULL，那么无论你是push_front还是push_back，都没有关系}。这将保持从前到后排序的出队。

如果正在读取的新数据大于前面的数据，则移除后面，将当前数据的迭代器推到前面；否则什么都不做

在迭代结束时，出队将拥有前五个元素的迭代器。

于 2012-09-17T20:29:36.480 回答
1

可能有一种更优雅的方式，但我现在很难找到它。你可以做这样的事情（未经测试，所以不能保证它开箱即用，特别是在极端情况下，但它应该）：

std::array<int, 5> indices = {-1,-1,-1,-1,-1};//-1 used as invalid index for cases where myVec.size()<5
for(int i = 0; i < myVec.size(); ++i)
{
    for(int j = 0; j < 5; ++j)
        if((indices[j] == - 1) || (myVec[i] > myVec[indices[j]]))
        {
            std::copy_backward(indices.begin() + j, indices.end() - 1, indices.end());
            indices[j] = i;
            break;
        }
}

它维护了 5 个最大元素的列表。对于向量的每个元素，它将从最大元素开始，测试新元素是否更大，如果是，则将索引向下移动并作为第一个插入，否则测试第二大元素，依此类推。不修改vector并O(n)以相当低的开销运行。

如果你不能使用 C++11，你总是可以使用std::vector（或者int[5]如果你真的想要）而不是std::array.

于 2012-09-17T20:30:39.970 回答
0

您将需要执行以下操作：

  int largestNumbers [5]{0, 0, 0, 0, 0};

  for each( const int i in data ){
  {
    for (int index = 0; index < 5; index++){
       if (i > largestNumber[index]){
          largestNumber[index] = i;
       }
     }
  }
于 2012-09-17T20:34:32.623 回答