my clean merge-sort Java solution


  • 0
    public List<Integer> countSmaller(int[] nums) {
            if(nums == null || nums.length == 0) return new ArrayList<>();
            int n = nums.length;
            int[] res = new int[n];
            int[] index = new int[n];
            for(int i = 0; i < n; i++) index[i] = i;
            
            mergeSort(nums, 0, n - 1, res, index);
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < n; i++) list.add(res[i]);
            return list;
        }
        
        private void mergeSort(int[] nums, int start, int end, int[] res, int[] index) {
            if(start == end) return;
            int mid = (start + end) / 2;
            mergeSort(nums, start, mid, res, index);
            mergeSort(nums, mid + 1, end, res, index);   
            
            int[] cache = new int[end - start + 1];
            int[] nIndex = new int[end - start + 1];
            int k = 0, j = mid + 1;
            int count = 0;
            
            for(int i = start; i <= mid; i++) {
                while(j <= end && nums[j] < nums[i]) {
                    count++;
                    cache[k] = nums[j];
                    nIndex[k] = index[j];
                    k++;
                    j++;
                }
                cache[k] = nums[i];
                nIndex[k] = index[i];
                res[index[i]] += count;
                k++;
            }
            while(j <= end) {
                cache[k] = nums[j];
                nIndex[k] = index[j];
                k++;
                j++;
            }
            
            System.arraycopy(cache, 0, nums, start, end - start + 1);
            System.arraycopy(nIndex, 0, index, start, end - start + 1);
        }

Log in to reply
 

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