Short solution in Java


  • 0
    F

    I used data compression and after a BIT.
    Time: O(n log n)
    Space: O(n)

    public List<Integer> countSmaller(int[] nums) {
        int size = nums.length;
        int values[] = nums.clone(), id = 0, bit[] = new int[size];
        Arrays.sort(values);
        Map<Integer, Integer> comp = new HashMap<>(size);
        for(int i = 0; i < size; i++) if(!comp.containsKey(values[i])) comp.put(values[i], id++);
        List<Integer> ans = new LinkedList<>();
        for(int i = 0, sum = 0; i < size; i++, sum = 0){
            for(int j = comp.get(nums[size - i - 1]) - 1; j >= 0; j = (j & (j + 1)) - 1) sum += bit[j];
            for(int j = comp.get(nums[size - i - 1]); j < size; j |= j + 1) bit[j] += 1;
            ans.add(0, sum);
        }
        return ans;
    }

Log in to reply
 

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