[leetcode] 295. Find Median from Data Stream

class MedianFinder {
public:
    /** initialize your data structure here. */
    multiset<int> nums;
    
    MedianFinder() {
        nums.clear();    
    }
    
    void addNum(int num) {
        nums.insert(num);
    }
    
    double findMedian() {
        
        int size = nums.size();
        multiset<int>::iterator it = nums.begin();
        
        advance(it, size/2);
        
        if(size%2){
            return *it;
        } else {
            return (double)(*it + *(--it))/2.0; 
        }
        
        return 1;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

 

우선 실행결과를 보니 턱걸이 수준이었습니다.

set을 사용해서 데이터 들어올떄마다 정렬되도록 진행하고 advance 명령어를 사용해 iterator를 원하는 위치로 이동해

다음 결과를 출력하는 가장 직관적인 방식으로 풀이하였습니다.

 

시간복잡도 : O(nlog(n))

 

 

최적의 해를 확인해보니 중간값을 기준으로 min_heap, max_heap을 각각 만들던데
이 방법을 사용하면 hash 높이가 절반으로 떨어지니 확실히 빨리지긴 할 것같다.

구현은 나중에,,,,