2

前面已经讨论过如何计算数字数组的中位数。例如，您可以参考使用 STL 容器进行中位数计算时的正确做法是什么？. 现在我有一个不同的问题，那就是如何在原始 STL 容器中获取中位数的索引。为了说明我的问题，我举一个例子：

vector<int> myarray;
myarray.push_back(3);
myarray.push_back(1);
myarray.push_back(100);
myarray.push_back( 20);
myarray.push_back(200);
int n = myarray.size()/2;
nth_element(myarray.begin(), myarray.begin()+n, myarray.end());
int median = myarray[n];

在上面的代码中，我可以获得中值，但无法在原始向量数组 (4) 中获得它的索引。有任何想法吗？谢谢！

4

4 回答 4

6

我认为没有直接的方法可以做到这一点。

您排序的向量已更改其顺序，因此在其中搜索将始终返回n。

您需要保存原始矢量的副本，然后在其中进行搜索。请记住，如果原始向量包含重复项，您将无法确切知道其中哪些实际上被放置在位置 n（如果这对您有任何相关性）。

作为替代方案，您可以查看 nth_element 的实现，并实现您自己的版本，该版本还报告找到的第 n 个元素的原始位置。

于 2012-07-19T08:16:38.223 回答
4

如果可以搜索元素

vector<int>::iterator itOfMedian = std::find(myarray.begin(), myarray.end(), median);
int index = itOfMedian - myarray.begin();

应该做的伎俩。

编辑

看来你有道理。nth_element对其参数向量进行排序...因此

vector<int> myArrayCopy = myarray;
// find median in myArrayCopy
vector<int>::iterator itOfMedian = std::find(myarray.begin(), myarray.end(), median);
int index = itOfMedian - myarray.begin();
于 2012-07-19T07:53:12.570 回答
3

您可以使用std::nth_element查找中值元素的迭代器。但是，这会对向量进行部分排序，因此您需要使用副本：

  std::vector<int> dataCopy = myarray;
  // we will use iterator middle later
  std::vector<int>::iterator middle = dataCopy.begin() + (dataCopy.size() / 2);
  // this sets iterator middle to the median element
  std::nth_element(dataCopy.begin(), middle, dataCopy.end());
  int nthValue = *middle;

现在它变得复杂了。您有一个对应于中位数的值。您可以搜索它的原始向量，并使用std::distance来获取索引：

std::vector<int>::iterator it = std::find(myarray.begin(), myarray.end(), nthValue);
std::vector<int>::size_type pos = std::distance(myarray.begin(), it);

nthValue但是，这仅在 in没有重复项的情况下才有效myarray。

于 2012-07-19T07:56:40.997 回答
1

很抱歉挖掘了一个老话题，但这是一个很好的方法。nth_element利用将按第一个元素对一对进行排序的事实；考虑到这一点，创建一个对的向量，其中对的第一部分是参与中位数计算的值，第二部分是索引。修改您的示例：

vector<pair<unsigned int, size_t>> myarray;
myarray.push_back(pair<unsigned int, size_t>(  3, 0));
myarray.push_back(pair<unsigned int, size_t>(  1, 1));
myarray.push_back(pair<unsigned int, size_t>(100, 2));
myarray.push_back(pair<unsigned int, size_t>( 20, 3));
myarray.push_back(pair<unsigned int, size_t>(200, 4));

int n = myarray.size()/2;
nth_element(myarray.begin(), myarray.begin()+n, myarray.end());

int median = myarray[n].first;
int medianindex = myarray[n].second;

当然myarray已经重新排列，所以myarray[medianindex]不是中位数。如果您之前制作了副本nth_element，medianindex则将是所需的索引。

于 2015-12-09T05:11:09.087 回答