concise c++ solution, use map


  • 1
    X
    class MedianFinder {
    public:
        /** initialize your data structure here. */
        MedianFinder() {
            size = 0;
    		idx = 0;
        }
        
        void addNum(int num) {
    		mymap[num]++;
    		if(mymap.size() == 1) median = mymap.begin();
    		int mid = median->first;
    		if(size > 0 && (size%2 == 0) && (num >= mid)){
    			if(idx < median->second - 1) idx++;
    			else{
    				median++;
    				idx = 0;
    			}
    		}
    		else if(size > 0 && (size%2) && (num < mid)){
    			if(idx > 0) idx--;
    			else{
    				median--;
    				idx = median->second - 1;
    			}
    		}
    		size++;
        }
        
        double findMedian() {
            if(size % 2) return (double)(median->first);
    		else{
    			double n1 = (double)(median->first);
    			auto it2 = median;
    			it2++;
    			double n2 = (idx < median->second - 1)? (double)(median->first) : double(it2->first);
    			return 0.5 * n1 + 0.5 * n2;
    		}
        }
    private:
    	map<int, int> mymap;
    	map<int, int>::iterator median;
    	int size, idx;
    };
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.