O(n*(log n)*(log n)) approach with binary index tree and binary search


  • 0
    C

    The idea is similar to most other solutions in sorting. The difference is, when preparing the final result, instead of paying a O(n^2) price, this way uses a binary index tree to dynamically maintain the indices to get O(n (log n)^2).

    At first, assume a uniform array of all 1's, and generate its corresponding binary index tree in O(n) time for all.

    When adding a person, imagine we mark his location from 1 to 0 in the uniform array mentioned in the first step, and update binary index tree. Its meaning is "mark this position occupied" so future searches should skip this location. It costs O(log n) per person.

    When determining the location of the current person, imagine we sum the binary tree, and use binary search in the sum array to find the correct index. Searching costs log n, and in each step it uses sum method of binary index tree which costs another log n, therefore the search cost becomes O((log n) ^2) per person.

    public class Solution {
        public int[][] reconstructQueue(int[][] people) {
            int[][]result = new int[people.length][2];
            Arrays.sort(people, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
            int[]bit = new int[people.length+1];
            for(int i = 1; i < bit.length; i++) {
                bit[i] = lastBit(i);
            }
            for(int[]p: people) {
                int order = binarySearch(bit, p[1] + 1, 1, bit.length);
                result[order - 1] = p;
                update(bit, order);
            }
            return result;
        }
    
        int sum(int[]bit, int order) {
            int result = 0;
            for(int i = order; i > 0; i -= lastBit(i)){
                result += bit[i];
            }
            return result;
        }
    
        void update(int[]bit, int order){
            for(int i = order; i < bit.length; i += lastBit(i)){
                bit[i]--;
            }
        }
    
        int lastBit(int n){
            return n & -n;
        }
    
        int binarySearch(int[]bit, int order, int begin, int end){ //find smallest i whose sum(bit, i) >= order
        	if(begin == end) return begin;
            if(begin+1 == end) return sum(bit, begin) >= order ? begin : end;
            int mid = begin + (end - begin >> 1);
            int midResult = sum(bit, mid);
            if(midResult >= order) return binarySearch(bit, order, begin, mid);
            else return binarySearch(bit, order, mid + 1, end);
        }
    }
    

Log in to reply
 

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