整数配列 nums が与えられた場合、指定された要件に従って新しい配列 counts を返してください。配列 counts は以下の性質を持つ必要があります：counts[i] の値は nums[i] の右側にある nums[i] より小さい要素の数です。

例 1：

<strong>入力：</strong>nums = [5,2,6,1]
<strong>出力：</strong>[2,1,1,0] 
<strong>説明：</strong>
5 の右側には <strong>2 </strong>つのより小さい要素があります (2 と 1)
2 の右側には <strong>1 </strong>つのより小さい要素があります (1)
6 の右側には <strong>1 </strong>つのより小さい要素があります (1)
1 の右側には <strong>0 </strong>つのより小さい要素があります

例 2：

<strong>入力：</strong>nums = [-1]
<strong>出力：</strong>[0]

例 3：

<strong>入力：</strong>nums = [-1,-1]
<strong>出力：</strong>[0,0]

制約：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

解法：マージソート

マージの過程で要素の位置が常に変化するため、計算した count[i] をどこに保存する必要があるのでしょうか？この問題に対処するために、各数字が元の配列内のどのインデックスに対応するかを記録する新しい配列 originalIndices を導入します。ソートを行う際には、元の配列 nums とこのインデックス配列を同時に変更します。

int[] から List への変換

List<Integer> result = Arrays.stream(resultArray).boxed().collect(Collectors.toList());

• Arrays.stream(arr) は IntStream.of(arr) に置き換えることができます。
• 1. Arrays.stream を使用して int[] を IntStream に変換します。
• 2. IntStream の boxed() を使用してボックス化します。これにより IntStream が Stream<Integer> に変換されます。
• 3. Stream の collect() を使用して Stream<T> を List<T> に変換します。これにより List<Integer> が得られます。

class RightSmallerCounter {
    public List<Integer> countSmaller(int[] inputArray) {
        int[] tempStorage = new int[inputArray.length];
        int[] resultCounts = new int[inputArray.length];
        int[] originalIndices = new int[inputArray.length];
        int[] tempIndices = new int[inputArray.length];
        
        // 元のインデックスを初期化
        for (int i = 0; i < inputArray.length; i++) {
            originalIndices[i] = i;
        }

        // マージソートを実行
        performMergeSort(inputArray, 0, inputArray.length - 1, tempStorage, resultCounts, originalIndices, tempIndices);
        
        // 結果をList<Integer>に変換
        List<Integer> finalResult = Arrays.stream(resultCounts).boxed().collect(Collectors.toList());
        return finalResult;
    }

    private void performMergeSort(int[] data, int leftBound, int rightBound, int[] tempArray, 
                                 int[] counts, int[] indices, int[] tempIndices) {
        if (leftBound == rightBound) {
            return;
        }
        
        int middle = leftBound + (rightBound - leftBound) / 2;
        performMergeSort(data, leftBound, middle, tempArray, counts, indices, tempIndices);
        performMergeSort(data, middle + 1, rightBound, tempArray, counts, indices, tempIndices);
        mergeSortedSubarrays(data, leftBound, middle, rightBound, tempArray, counts, indices, tempIndices);
    }

    private void mergeSortedSubarrays(int[] array, int left, int mid, int right, 
                                    int[] temp, int[] count, int[] index, int[] tempIndex) {
        // 一時配列にデータをコピー
        for (int i = left; i <= right; i++) {
            temp[i] = array[i];
            tempIndex[i] = index[i];
        }
        
        int leftPointer = left;
        int rightPointer = mid + 1;
        
        for (int i = left; i <= right; i++) {
            if (leftPointer > mid) {
                // 左側のサブ配列が使い切れた場合
                index[i] = tempIndex[rightPointer];
                array[i] = temp[rightPointer++];
            } else if (rightPointer > right) {
                // 右側のサブ配列が使い切れた場合
                count[tempIndex[leftPointer]] += right - mid;
                index[i] = tempIndex[leftPointer];
                array[i] = temp[leftPointer++];
            } else if (temp[leftPointer] <= temp[rightPointer]) {
                // 左側の要素が右側の要素以下の場合
                count[tempIndex[leftPointer]] += right - mid;
                index[i] = tempIndex[leftPointer];
                array[i] = temp[leftPointer++];
            } else {
                // 右側の要素が左側の要素より小さい場合
                index[i] = tempIndex[rightPointer];
                array[i] = temp[rightPointer++];
            }
        }
    }
}

複雑さの分析：

• 時間計算量：O(N log N)、ここで N は配列 nums の長さです。
• 空間計算量：O(N)、補助配列 temp、count、index、tempIndex がそれぞれ O(N) の追加領域を使用するため、O(4N) = O(N) となります。