목록 내의 중앙값의 위치

Question

정렬되지 않은 배열이 있으며 중간 값의 위치가 필요합니다. O (n)에서 주어진 배열의 중앙값을 계산하는 알고리즘이 몇 가지 있지만 모든 배열에 중간 정렬과 무작위 선택의 중간 정렬과 같은 정렬 순서가 포함되어 있습니다.

저는 중간자 자체에 관심이 없습니다. 배열 내의 위치 만 관심을 갖습니다.

O (n)에서이 작업을 수행 할 수있는 방법이 있습니까? 모든 스왑을 추적하면 막대한 오버 헤드가 발생하므로 다른 솔루션을 찾고 있습니다.

Answer 1

의 당신은 데이터의 배열이 있다고 가정 해 봅시다, 당신은 그 중간 찾을 싶습니다과 같이

double data[MAX_DATA] = ... 

인덱스의 배열을 만들고, 그리고 자신의 위치에 각각의 인덱스를 초기화 :

• 원래 알고리즘 :

  int index[MAX_DATA]; 
  for (int i = 0 ; i != MAX_DATA ; i++) { 
      index[i] = i; 
  } 
  

  이제 다음과 같이 변경과 함께 선형 평균 알고리즘을 구현 원래 알고리즘 스왑 data[i] 및 data[j]는 index[i] 및 index[j] 대신 교체시에 data[j]data[i]를 비교 data[index[j]]

• -data[index[i]]의 비교로 대체. data 요소 이후

그들의 위치에 항상 남아있는 일부 요소 어레이에서의 위치가 다른 장소로 이동하는 대신, 비 변형 배열의 중간의 위치를 ​​생성 할 것이다 수정 알고리즘.

C++에서 대신 인덱스의 포인터로이를 구현 할 수 있으며, 다음과 같이 포인터의 컨테이너에 std::nth_element를 사용

여기

vector<int> data = {1, 5, 2, 20, 10, 7, 9, 1000}; 
vector<const int*> ptr(data.size()); 
transform(data.begin(), data.end(), ptr.begin(), [](const int& d) {return &d;}); 
auto mid = next(ptr.begin(), data.size()/2); 
nth_element(ptr.begin(), mid, ptr.end(), [](const int* lhs, const int* rhs) {return *lhs < *rhs;}); 
ptrdiff_t pos = *mid - &data[0]; 
cout << pos << endl << data[pos] << endl; 

가 link to a demo on ideone이다.

Answer 2

무한한 수의 스트림에서 중간 값을 추적하기위한 O (n log n) 알고리즘이 있습니다. 목록을 변경하지 않으려는 경우 스트림을 처리 할 수 ​​있습니다. 알고리즘에는 두 개의 힙이 포함됩니다. 하나는 항상 하반부의 최대 수를 가리키고 다른 하나는 상반부의 최소 수를 나타냅니다. 알고리즘은 여기에서 설명합니다 : http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/. 최소한의 사용자 지정으로 동일한 코드를 사용할 수 있습니다.

Answer 3

여기서 인덱스의 2 어레이를 생성하는 예를 작동, 그리고 std::nth_element 통해 입력 어레이의 중간 및 간접 비교

#include <algorithm> 
#include <string> 
#include <vector> 
#include <iostream> 
#include <iterator> 

int main() 
{ 
    // input data, big and expensive to sort or copy 
    std::string big_data[] = { "hello", "world", "I", "need", "to", "get", "the", "median", "index" };  

    auto const N = std::distance(std::begin(big_data), std::end(big_data)); 
    auto const M = (N - 1)/2; // 9 elements, median is 4th element in sorted array 

    // generate indices 
    std::vector<int> indices; 
    auto value = 0; 
    std::generate_n(std::back_inserter(indices), N, [&](){ return value++; }); 

    // find median of input array through indirect comparison and sorting 
    std::nth_element(indices.begin(), indices.begin() + M, indices.end(), [&](int lhs, int rhs){ 
     return big_data[lhs] < big_data[rhs]; 
    }); 
    std::cout << indices[M] << ":" << big_data[indices[M]] << "\n"; 

    // check, sort input array and confirm it has the same median 
    std::sort(std::begin(big_data), std::end(big_data)); 
    std::cout << M << ":" << big_data[M] << "\n"; 
} 

온라인 output를 찾는다.

이 알고리즘은 입력 데이터에 O(N) 인 std::generate_n과 std::nth_element의 합계이기 때문에 O(N)의 복잡성이 보장됩니다.