Leetcode: 데이터 흐름 의 중위 수

Leetcode: 데이터 흐름 의 중위 수
 
중위 수 는 서열 표 중간의 수 이다.목록 길이 가 짝수 라면, 중위 수 는 중간 두 수의 평균 값 이다.
예컨대
[2,3,4] 중위 수
[2, 3] 의 중위 수 는 (2 + 3) / 2 = 2.5 이다.
다음 두 가지 조작 을 지원 하 는 데이터 구 조 를 설계 합 니 다.

void addNum (int num) - 데이터 흐름 에서 하나의 정 수 를 데이터 구조 에 추가 합 니 다.

double findMedian () - 현재 모든 요소 의 중위 수 를 되 돌려 줍 니 다.

예시:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

진급:

만약 에 데이터 흐름 중의 모든 정수 가 0 에서 100 범위 안에 있다 면 당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?

만약 에 데이터 흐름 에서 99% 의 정수 가 0 에서 100 범위 안에 있다 면 당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?

 
사고 1: 모든 정렬 에서 중간 수 를 취한 다.
데 이 터 를 삽입 하면 모든 데 이 터 를 다시 정렬 하 는 것 으로 비용 이 매우 많이 든다.
사고방식 2: 큰 무더기 + 작은 무더기
중간 두 개의 숫자 만 필요 하기 때문에 데 이 터 를 반 으로 나 눌 수 있 고 앞 반 은 후반 보다 작 으 며 앞 반 은 큰 지붕 더 미 를 만 들 고 후반 에는 작은 지붕 더 미 를 만 들 수 있다.앞 에 쌓 인 요소 의 개수 가 뒤 쌓 인 요소 의 개수 보다 크 거나 같은 제약 조건 을 유지 합 니 다.
요 소 를 새로 삽입 할 때 모두 4 가지 상황 이 있 습 니 다.
첫 번 째 는 앞 더 미 를 직접 넣 는 것 이 고, 두 번 째 는 바로 뒷 더 미 를 넣 는 것 이다. 세 번 째 는 앞 더 미 를 넣 고 뒷 더 미 를 넣 는 것 이다. 새로운 요 소 는 앞 더 미 를 교체 하고, 네 번 째 는 뒤 더 미 를 쌓 는 것 이다.
네 가지 조작의 조건 을 모두 가 매 거 할 수 있다.
주의해 야 할 것 은 더미 에 요 소 를 삽입 하려 면 다시 쌓 아야 한 다 는 것 이다.쌓 인 요 소 를 새로운 요소 로 바 꾸 면 쌓 인 요 소 를 직접 조정 하면 된다.
쌓 기 작업: 쌓 인 중간 위치 요소 부터 첫 번 째 요 소 를 시작 으로 쌓 기 조정 작업 을 합 니 다.
쌓 기 작업 조정: 특정한 요 소 를 시작 으로 좌우 아이의 위 치 를 교환 하고 잎 노드 나 좌우 아이의 노드 와 쌓 기 조건 을 만족 시 킬 때 까지 재 귀 합 니 다.
코드 는 다음 과 같 습 니 다:

class MedianFinder {
    vector foreVec,postVec;
public:
    /** initialize your data structure here. */
    MedianFinder() {
        
    }
    
    void addNum(int num) {
        if(foreVec.empty()){
            foreVec.push_back(num);
        }else if(postVec.empty()){
            if(num>=foreVec.front())     postVec.push_back(num);
            else{
                postVec.push_back(foreVec.front());
                foreVec.front()=num;
            }
        }else{
            if(foreVec.size()==postVec.size()){
                if((num>foreVec.front() && num=postVec.front()){
                    foreVec.push_back(postVec.front());
                    buildHeap(foreVec,true);
                    postVec.front()=num;
                    adjustHeap(postVec,0,false);
                }    
            }else{
                assert(foreVec.size()>postVec.size());
                if(num>=foreVec.front()){
                    postVec.push_back(num);
                    buildHeap(postVec,false);
                }else{
                    postVec.push_back(foreVec.front());
                    buildHeap(postVec,false);
                    
                    foreVec.front()=num;
                    adjustHeap(foreVec,0,true);
                }
            }
            
            
            
        }
       
    }
    
    double findMedian() {
        double res=0.0;
        if(foreVec.size()==postVec.size()){
            res+=foreVec.front();
            res+=postVec.front();
            res/=2;
        }else{
            res=foreVec.front();
        }
        return res;
    }
    
    void buildHeap(vector& v,bool bigTop){
        for(int i=v.size()/2;i>=0;--i){
            adjustHeap(v,i,bigTop);
        }
    }
    
    void adjustHeap(vector& v,int start,bool bigTop){
        int len=v.size();
        int i=start;
        auto iter=v.begin();
        while(i*(iter+left)) ||(!bigTop && right*(iter+*pBigger))){
                swap(*(iter+i),*(iter+*pBigger));
                i=*pBigger;
            }else{
                break;
            }
        }
        
    }
};

 
진급 에 대하 여
1。만약 데이터 흐름 중의 모든 정수 가 0 에서 100 범위 내 에 있다 면, 당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?
쌓 을 필요 가 없습니다. int [101] arr 로 특정한 데이터 가 나타 난 횟수 를 기록 합 니 다.중위 수 를 뽑 으 려 면 처음으로 배열 을 옮 겨 다 니 며 총 개 수 를 누적 해 야 한다.그 다음 에 2 로 나 누 어 찾 아야 할 수의 위치 p 를 얻 고 홀수 인지 짝수 인지 알 고 두 번 째 로 배열 을 옮 겨 다 니 며 p - = arr [i], p 가 1 과 0 으로 변 할 때 각각 i, j 를 기록 합 니 다.홀수 개 수 는 j 를 되 돌려 주 고 짝수 개 수 는 (i + j) / 2 를 되 돌려 줍 니 다.
2。만약 데이터 흐름 중 99% 의 정수 가 0 에서 100 범위 내 에 있다 면 당신 은 어떻게 당신 의 알고리즘 을 최적화 할 것 입 니까?
마찬가지 로 1 의 사고방식 을 참조 하여 int [102] arr 로 데이터 가 나타 난 횟수 를 기록 하고 arr [101] 은 100 보다 많은 횟수 를 기록한다.데이터 가 주로 100 과 이내 에 분포 되 어 있 기 때문에 중간의 2 개 수 는 100 또는 이내 인지 알 수 있 고 1 의 알고리즘 은 여전히 유효 하 다.