STL을 사용하여 중앙값의 지수를 얻는 방법은 무엇입니까?

Question

디지털 숫자 배열의 중앙값을 계산하는 방법은 이전에 논의되었습니다. 예를 들어, What is the right approach when using STL container for median calculation?을 참조 할 수 있습니다. 이제는 다른 질문이 있습니다. 원래 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) : 내 질문을 설명하기 위해, 나는 예를 제공합니다. 어떤 아이디어? 감사!

Answer 1

는 요소 트릭을 할해야

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

를 검색 할 수 accapteble 경우.

수정

여기에 요점이있는 것으로 보입니다. 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(); 

Answer 2

당신은 중간 요소에 대한 반복자를 찾을 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); 

합니다.

Answer 3

나는 그렇게 할 수있는 직접적인 방법이 없다고 생각합니다.

정렬 한 벡터의 순서가 변경되어 검색 할 때 항상 n이 반환됩니다.

원본 벡터의 복사본을 저장하고 검색해야합니다. 원래 벡터에 중복 된 것이 포함되어 있다면 실제로 그 중 어느 것이 실제로 n 위치에 놓 였는지 정확히 알 수 없습니다 (이는 관련성이있는 경우).

대신 nth_element의 구현을 살펴보고 발견 된 n 번째 요소의 원래 위치를보고하는 고유 한 버전을 구현할 수 있습니다.

Answer 4

오래된 주제를 찾아서 죄송하지만, 여기에 좋은 방법이 있습니다. nth_element이 첫 번째 요소로 쌍을 정렬한다는 사실을 악용합니다. 이를 염두에두고 쌍의 첫 번째 부분이 중간 계산에 참여할 값이고 두 번째 부분이 인덱스 인 쌍의 벡터를 만듭니다. 귀하의 예제를 수정 : 물론 myarray의

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[medianindex]가 중간 없습니다. nth_element 전에 사본을 만든 경우 medianindex이 원하는 색인이됩니다.