my 9 ms java solution with merge sort method.


  • 0
    J

    """
    public class Solution {
    int[] count;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return result;
        }
        count = new int[nums.length];
        int[] indices = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            indices[i] = i;
        }
        int[] helper = new int[indices.length];
        mergeSort(nums, indices, helper, 0, nums.length - 1);
        for (int i : count) {
            result.add(i);
        }
        return result;
    }
    
    private void mergeSort(int[] nums, int[] indices, int[] helper, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(nums, indices, helper, left, mid);
        mergeSort(nums, indices, helper, mid + 1, right);
        combine(nums, indices, helper, left, mid, right);
    }
    
    private void combine(int[] nums, int[] indices, int[] helper, int left, int mid, int right) {
        System.arraycopy(indices, left, helper, left, right + 1 - left);
        int leftIndex = left;
        int rightIndex = mid + 1;
        while (leftIndex <= mid && rightIndex <= right) {
            if (nums[helper[leftIndex]] <= nums[helper[rightIndex]]) {
                count[helper[leftIndex]] += rightIndex - mid - 1;
                indices[left++] = helper[leftIndex++];
            } else {
                indices[left++] = helper[rightIndex++];
            }
        }
        while (leftIndex <= mid) {
            count[helper[leftIndex]] += rightIndex - mid - 1;
            indices[left++] = helper[leftIndex++];
        }
    }
    

    }
    """


Log in to reply
 

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