My O(nlogn) solution with Binary Index Tree


  • 0
    K

    Just need to maintain the empty positions befor x ([1,x]) using BIT and the update operator's complexity is O(logn).

    class Solution {
    public:
    	int n, bit[1100];
    	int lowbit(int x) { return x & (-x); }
    	void update(int i, int x) {
    		while(i <= n) {
    			bit[i] += x;
    			i += lowbit(i);
    		}
    	}
    	int sum(int i) {
    		int ret = 0;
    		while(i) {
    			ret += bit[i];
    			i -= lowbit(i);
    		}
    		return ret;
    	}
    	int lb(int val) {
    		int lo = 1, hi = n;
    		while(lo <= hi) {
    			int mid = (lo + hi) >> 1;
    			int x = sum(mid);
    			if(x >= val) hi = mid - 1;
    			else lo = mid + 1;
    		}
    		return lo;
    	}
    	static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    		if(a.first != b.first) return a.first < b.first;
    		return a.second > b.second;
    	}
    	vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
    		pair<int, int> ret[1100];
    		memset(bit, 0, sizeof(bit));
    		n = people.size();
    		for(int i = 2; i <= n; i++) update(i, 1);
    		sort(people.begin(), people.end(), cmp);
    		for(int i = 1; i <= n; i++) {
    			int pos = lb(people[i-1].second+1);
    			update(pos, -1);
    			ret[pos-1].first = people[i-1].first;
    			ret[pos-1].second = people[i-1].second;
    		}
    		people.clear();
    		for(int i = 1; i <= n; i++) people.push_back(ret[i]);
    		return people;
    	}
    };
    

  • 0
    F

    Actually your complexity is O(nlognlogn). You used both binary search and binary indexed tree.


  • 0
    P

    Can you explain your algorithm?


Log in to reply
 

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