한 함수 에 무 작위 로 전달 되 는 숫자 를 만 들 고 프로그램 을 써 서 이 수의 중위 수 를 찾 아 유지 합 니 다.

Cracking the coding interview--Q20.9
March 6, 2013
글 쓴 이: Hawtein
출처:http://hawstein.com/posts/20.9.html
성명: 본 고 는 다음 과 같은 협 의 를 통 해 권한 을 부여 한다.  자유 전재 - 비상 용 - 비 파생 - 서명 유지 | Creative Commons BY - NC - ND 3.0 ，전재 하 다.
제목.
원문:
Numbers are randomly generated and passed to a method. Write a program to find and maintain the median value as new values are generated.
번역문:
한 함수 에 무 작위 로 전달 되 는 숫자 를 만 들 고 프로그램 을 써 서 이 수의 중위 수 를 찾 아 유지 합 니 다.
해답
방법 1
가장 간단 하고 직관 적 인 방법 은 충분 한 배열 A 로 이 수 를 유지 하고 오름차 순 으로 배열 하 는 것 이다.이렇게 되면 O (1) 의 시간 으로 중위 수 를 찾 을 수 있다.다음은 그림 입 니 다.

  ：1 3 5            ：1 3 5 7
  ：0 1 2            ：0 1 2 3
   ：A[n/2]         ：(A[(n-1)/2] + A[n/2])/2

이 방법 은 새로운 요 소 를 삽입 하 는 데 O (n) 의 시간 이 필요 합 니 다. 원래 질서 있 는 배열 에서 적당 한 위 치 를 찾 아 삽입 하고 그 보다 큰 요 소 를 뒤로 이동 해 야 합 니 다.
방법 2
이 수 를 최대 더미 (또는 최소 더미) 로 유지 합 니 다.그러면 새로운 요 소 를 삽입 하 는 데 O (logn) 의 시간 이 필요 합 니 다. 방법 보다 좋 습 니 다.그러나 중위 수 를 얻 으 려 면 먼저 정렬 해 야 한다. 시간 복잡 도 O (nlogn).
방법
더 미 를 사용 하여 데 이 터 를 유지 하 는 것 은 좋 은 선택 입 니 다. 새로운 요 소 를 삽입 하 는 데 O (logn) 의 시간 만 필요 하지만 중위 수 를 취 하 는 데 시간 이 걸 리 고 정렬 에 시간 이 많이 걸 립 니 다.정렬 을 안 할 수 있 는 방법 이 없 을까요?우 리 는 중위 수 는 질서 있 는 서열 에서 중간 에 있 는 숫자 로 좌우 양쪽 의 수가 비슷 하 다 는 것 을 안다.방법 1 의 설명도 에서 알 수 있 듯 이 배열 의 크기 n 이 홀수 일 때 중위 수 는 질서 있 는 배열 의 중간 에 있 는 숫자 이 고 n 이 짝수 라면 중간 두 수의 평균 수 이다.그것 은 서열 중간의 하나 또는 두 개의 수 와 만 관련 이 있 고 다른 요소 와 는 무관 하 다.그러면 만약 에 제 가 가장 큰 더미 로 중위 수 왼쪽 의 수 (포함) 를 유지 하고 가장 작은 더미 로 중위 수 오른쪽 을 유지 합 니 다.n 이 짝수 일 때 나 는 왼쪽 의 가장 큰 숫자 를 오른쪽 의 가장 작은 숫자 와 2 를 더 하면 된다.왼쪽 의 최대 수 는 가장 큰 더미 의 꼭대기 요소 이 고 오른쪽 의 최소 수 는 가장 작은 더미 의 꼭대기 요소 이다.n 이 홀수 일 때 가장 많은 원소 가 가장 작은 원소 보다 1 이 많 으 면 가장 많은 원소 가 중위 수 이다.가장 작은 원소 가 가장 많은 원소 보다 1 이 많 으 면 가장 작은 원소 가 중위 수 이다.새로운 요 소 를 삽입 할 때 우 리 는 두 개의 더 미 를 유지 하고 그 더미 에 있 는 요소 의 수량 차이 가 1 을 초과 하지 않도록 하면 된다.
이렇게 되면 새로운 요 소 를 삽입 하 는 시간 은 O (logn) 의 시간 이 고, 중위 수 를 얻 는 데 는 O (1) 의 시간 이 필요 하 며, 방법 1 과 방법 2 보다 우수 합 니 다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstdlib>
using namespace std;

class Median{
private:
    priority_queue<int,vector<int>,less<int> > max_heap;//    
    priority_queue<int,vector<int>,greater<int> > min_heap;//    

public:
    void Insert(int v);
    int GetValue();
};

void Median::Insert(int v){
    if(max_heap.empty() && min_heap.empty())
        max_heap.push(v);
    else if(!max_heap.empty() && min_heap.empty())
        max_heap.push(v);
    else if(max_heap.empty() && !min_heap.empty())
        min_heap.push(v);
    else{
        if(v < max_heap.top())
            max_heap.push(v);
        else
            min_heap.push(v);
    }
    //  ，               1
    //   max_heap.size()-min_heap.size()>1
    //  size    unsigned  ，            ，   false
    //           ，   true，   
    while(max_heap.size() > min_heap.size()+1){
        int data = max_heap.top();
        min_heap.push(data);
        max_heap.pop();
    }
    while(min_heap.size() > max_heap.size()+1){
        int data = min_heap.top();
        max_heap.push(data);
        min_heap.pop();
    }
}

int Median::GetValue(){//    int，     ，    float
    if(max_heap.empty() && min_heap.empty())
        return (1<<31); //    ，  int   
    if(max_heap.size() == min_heap.size())
        return (max_heap.top()+min_heap.top()) / 2;
    else if(max_heap.size() > min_heap.size())
        return max_heap.top();
    else
        return min_heap.top();
}

int main(){
    srand((unsigned)time(0));
    Median md;
    vector<int> vi;
    int num = rand() % 30; //   30      
    for(int i=0; i<num; ++i){
        int data = rand() % 100; //   100   
        vi.push_back(data);
        md.Insert(data);
    }
    sort(vi.begin(), vi.end());
    for(int i=0; i<num; ++i)
        cout<<vi.at(i)<<" "; //     
    cout<<endl<<md.GetValue()<<endl; //   
    return 0;
}