Java short Binary Indexed Tree solution, time O(NlogN) space O(N)


  • 0
    A
    public class Solution {
        public List<Integer> countSmaller(int[] nums) {
            if (nums == null || nums.length == 0) return new ArrayList<>();
            int[] tmp = nums.clone();
            Arrays.sort(tmp);
            int[] bit = new int[nums.length + 1];
            for (int i : nums) addVal(bit, Arrays.binarySearch(tmp, i), 1);
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) {
                int idx = Arrays.binarySearch(tmp, nums[i]);
                addVal(bit, idx, -1);
                res.add(query(bit, idx - 1));
            }
            return res;
        }
    
        // add val to the ith element, O(logN)
        public void addVal(int[] bit, int i, int val) {
            for (i += 1; i < bit.length; i += i & -i) bit[i] += val;
        }
    
        // query the range sum of [0, i], O(logN)
        public int query(int[] bit, int i) {
            int res = 0;
            for (i += 1; i > 0; i -= i & -i) res += bit[i];
            return res;
        }
    }

Log in to reply
 

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