如何用STL獲得中位數的指數？

以前討論過如何計算數字數組的中位數。例如，您可以參考What is the right approach when using STL container for median calculation?。現在我有一個不同的問題，那就是如何獲得原始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）。有任何想法嗎？謝謝！

來源

2012-07-19 feelfree

爲什麼你認爲中位數是向量中的元素之一？ – 2012-07-19 07:59:24

如果使用正確（假設爲奇數長度的數組），則'n_element'會爲您提供一個到中值的迭代器。通過迭代器和'std :: distance'，你可以得到你想要的。請參閱下面的答案。 – juanchopanza 2012-07-19 08:11:26

@EitanT這裏我舉一個例子，其中元素的數量是奇數。擴展元素數量均勻的情況很簡單。 – feelfree 2012-07-19 08:43:34

如果accapteble搜索元素

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-19 07:53:12 Matthias

無需使用find。 'nth_element'給元素提供了一個迭代器。 OP只是沒有讓迭代器回來。 – juanchopanza 2012-07-19 08:12:16

我試過了，但失敗了。原因是因爲調用nth_element函數也可以改變myarray向量。 – feelfree 2012-07-19 08:17:25

@feelfree對不起，我誤解了這個問題。如果您想在原始矢量中使用索引，請按照上述操作，但在調用nth_element之前使用原件的副本。 – juanchopanza 2012-07-19 08:28:47

您可以使用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獲得索引：如果沒有的nthValue重複在myarray

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

然而，這僅適用。

來源

2012-07-19 07:56:40 juanchopanza

我試過這些代碼，但失敗了。 – feelfree 2012-07-19 08:08:44

@feelfree什麼都失敗了？ – juanchopanza 2012-07-19 08:15:38

std :: distance（data.begin（），middle）將始終爲（data.size（）/ 2）。調用nth_element不會更改迭代器，它會更改數據。 – Timbo 2012-07-19 08:23:55

我認爲沒有直接的方法來做到這一點。

您排序的向量已更改其順序，以便在該搜索中始終返回n。

您需要保存您的原始矢量的副本，然後在其中進行搜索。請記住，如果原始矢量包含重複項，則不會確切知道其中哪些實際放置在位置n（如果這對您有任何相關性）。

作爲替代方案，您可以查看nth_element的實現，並實現您自己的版本，該版本還會報告找到的第n個元素的原始位置。

來源

2012-07-19 08:16:38 Timbo

對不起，挖掘一個老話題，但這是一個很好的方式來做到這一點。利用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-09 05:11:09 nonbasketless

如果您可以使用其他答案中顯示的方法獲取O（1）中的中值索引，我就不會在存儲索引時看到這一點。 – juanchopanza 2017-11-25 12:49:20

如何用STL獲得中位數的指數？

回答

相關問題