Share my soultion c++ 140ms(平衡树裸题)


  • 0
    B
    class MedianFinder {
    public:
    	const int INF = ~0u >> 1;
    	MedianFinder() { null = new Node(INF, 0, NULL); root = null; }
    	~MedianFinder() { clear(root), delete null; }
    	void addNum(int num) {
    		insert(root, num);
    	}
    	double findMedian() {
    		int t = root->s;
    		if (t & 1) {
    			return (double)kth((t >> 1) + 1);
    		} else {
    			int v1 = kth(t >> 1);
    			int v2 = kth((t >> 1) + 1);
    			return (v1 + v2) / 2.0;
    		}
    	}
    private:
    	struct Node {
    		int v, s, c;
    		Node *ch[2];
    		Node() = default;
    		Node(int _v_, int _s_, Node *p) {
    			v = _v_, s = c = _s_;
    			ch[0] = ch[1] = p;
    		}
    		inline void push_up() {
    			s = ch[0]->s + ch[1]->s + c;
    		}
    		inline int cmp(int x) const {
    			return x == v ? -1 : x > v;
    		}
    	}*root, *null;
    	inline Node *newNode(int v) {
    		Node *x = new Node(v, 1, null);
    		return x;
    	}
    	inline void rotate(Node *&x, int d) {
    		Node *k = x->ch[!d]; x->ch[!d] = k->ch[d], k->ch[d] = x;
    		k->s = x->s; x->push_up(); x = k;
    	}
    	inline void Maintain(Node *&x, int d) {
    		if (!x->s) return;
    		if (x->ch[d]->ch[d]->s > x->ch[!d]->s) rotate(x, !d);
    		else if (x->ch[d]->ch[!d]->s > x->ch[!d]->s) rotate(x->ch[d], d), rotate(x, !d);
    		else return;
    		Maintain(x, 0), Maintain(x, 1);
    	}
    	inline void insert(Node *&x, int v) {
    		if (!x->s) { x = newNode(v); return; }
    		x->s++;
    		int d = x->cmp(v);
    		if (-1 == d) { x->c++; return; }
    		insert(x->ch[d], v);
    		x->push_up();
    		Maintain(x, d);
    	}
    	inline void clear(Node *&x) {
    		if (x->s) clear(x->ch[0]), clear(x->ch[1]), delete x;
    	}
    	inline int kth(int k) {
    		Node *x = root;
    		for (int t = 0; x->s;) {
    			t = x->ch[0]->s;
    			if (k <= t) x = x->ch[0];
    			else if (t + 1 <= k && k <= t + x->c) break;
    			else k -= t + x->c, x = x->ch[1];
    		}
    		return x->v;
    	}
    };

Log in to reply
 

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