leetcode-剑指41-OK

// language C with STL(C++)
// 剑指41
// https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/


class MedianFinder {
public:
	int what[25000];
    int next = 0;
    /** initialize your data structure here. */

    int FindPosition(int num){
    	// res 满足 what[res-1]<= num, what[res]>num,这两个数都可能不存在
    	if(what[0] > num) return 0;
    	if(what[next-1]<=num) return next;
    	int res = 1;
    	for(; res<next; res++){
    		if((what[res-1] <= num) &&(what[res]>num))
    			return res;
    	}
        // printf("(%d)",next);
        // display();
    	return -1;	// 出错
    }

    void display(){
        for(int i =0; i <next; i++)
            printf("%dT", what[i]);
        printf("
");
    }

    MedianFinder() {
    }
    
    void addNum(int num) {
    	// 相当于找到num所在位置index，然后index~next-1位置的数全都后移一位
    	if(next== 0){
    		what[next] = num;
            next++;
    	}else{
	    	int position = FindPosition(num);
            // printf("%d#",position);
	    	for(int i=next; i>position; i--){
	    		what[i] = what[i-1];
	    	}
	    	what[position] = num;
	    	next++;
	    }
    }
    
    double findMedian() {
    	double res;
    	if(next%2 ==1)
    		res = what[next/2];
    	else{
    		// printf("%d-", what[next/2-1]);
    		// printf("%d-", what[next/2]);
    		res = what[next/2-1] + what[next/2];
            // printf("%d-", res);
            res /=2;
    	}
    	return res;
    }
};

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