315. Count of Smaller Numbers After Self - pangeneral/leetcode-notebook GitHub Wiki

The basic idea is using merge sort to calculate the smaller number during the merge process of two sub arrays. Of course there are some details we need to consider:

  1. We define IndexInteger to record the index of each number in the original array
  2. The array is sorted descend so that we can calculate the smaller number after self in O(1) time
class IndexInteger {
    int value;
    int index;

    public IndexInteger(int index, int value) {
	this.index = index;
	this.value = value;
    }
}

public void count(int[] resultArray, IndexInteger[] integerArray, int begin, int end) {
    if( begin < end ){
	int mid = (begin + end) / 2;
	count(resultArray, integerArray, begin, mid);
	count(resultArray, integerArray, mid + 1, end);
	IndexInteger tempArray[] = new IndexInteger[end - begin + 1];
	int index = 0, leftIndex = begin, rightIndex = mid + 1;
	while( leftIndex <= mid && rightIndex <= end ) {
	    if( integerArray[leftIndex].value <= integerArray[rightIndex].value )
		tempArray[index++] = integerArray[rightIndex++];
	    else { 
		resultArray[integerArray[leftIndex].index] += end - rightIndex + 1;
		tempArray[index++] = integerArray[leftIndex++];
	    }
	}
	while( leftIndex <= mid )
	    tempArray[index++] = integerArray[leftIndex++];
	while( rightIndex <= end )
	    tempArray[index++] = integerArray[rightIndex++];
	for(int i = 0; i < tempArray.length; i++)
	    integerArray[i + begin] = tempArray[i];
    }
}

public List<Integer> countSmaller(int[] nums) {
    int resultArray[] = new int[nums.length];
    List<Integer> resultList = new ArrayList<Integer>();
    IndexInteger integerArray[] = new IndexInteger[nums.length];
    for(int i = 0; i < nums.length; i++) {
	integerArray[i] = new IndexInteger(i, nums[i]);
    }
    count(resultArray, integerArray, 0, integerArray.length - 1);
    for(int i = 0; i < resultArray.length; i++)
	resultList.add(resultArray[i]);
    return resultList;
}
⚠️ **GitHub.com Fallback** ⚠️