「力扣」第 315 题：计算右侧小于当前元素的个数

题目地址	题解
LeetCode 第 315 题：计算右侧小于当前元素的个数	归并排序 + 索引数组（Python 代码、Java 代码）

归并排序（索引数组）

如果有学习过一个数组的“逆序对”如何计算的朋友，对求解这道问题应该不陌生。求解“逆序对”的关键在于：当其中一个数字放进最终归并以后的有序数组中的时候，这个数字与之前看过的数字个数（或者是未看过的数字个数）可以直接统计出来，而不必一个一个数”。

“归并排序”完成以后，原数组的“逆序数”也数出来了。

下面这句话很重要：

回到本题，本题让我们求“在一个数组的某个元素的右边，比自己小的元素的个数”，因此，我们就应该在“前有序数组”的元素出列的时候，数一数“后有序数组”已经出列了多少元素，因为这些已经出列的元素都比当前出列的元素要小（或者等于）。

发现问题

不过题目中要求我们要具体计算到元素级别。“归并排序”完成以后，原始数组的位置就已经变化了，因此如何定位元素是关键。

想一想这一列问题是怎么解决的

一个元素在算法的执行过程中位置发生变化，我们还想定位它，这样的场景我们在“最小索引堆”中曾经学习过，从中得到启发，不妨也设置一个“索引数组”吧。使用“索引数组”的关键在于：

“原始数组”不变，用于比较两个元素的大小，真正位置变换的是“索引数组”。

下面我尝试解释一下“索引数组”的使用方法：

为了完成“索引数组”的归并，我们还需要一个“索引数组”长度的临时数组，把索引数组的值复制过去，比较完成以后，再赋值回“索引数组”。具体请看下面的代码。

编码注意事项

一、可以复习一下“归并排序”的细节。

1、如果“前有序数组”和“后有序数组”直接合并的时候，就有序，就不必归并；
2、在“归并”的时候，全局使用一个临时存储数组，而不必每一个归并都新建临时的存储空间。

二、出列一个元素的时候，马上得到右边比自己小的元素的个数，是通过不同的指针之间的距离得到的。

在编码的时候，建议在草稿纸上写写画画，用具体的数值带进去，才能确保你计算的指针之间的距离正确。例如我写的 Python 代码 res[indexes[i]] += (right - mid) 和 res[indexes[i]] += (r - mid - 1) 这两句代码的计算，我就是在草稿纸上画出来的。

三、如果你写过“逆序数”的计算的代码，你就会发现，“逆序数”的计算可以在“前有序数组”元素出列的时候计算逆序数，也可以在“后有序数组”元素出列的时候计算逆序数，你可以比较一下它们在编码时候的不同之处。下面是我写“逆序数”的计算代码写的草稿。

参考代码：

Python 代码：

class Solution:
    def countSmaller(self, nums):
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        indexes = [i for i in range(size)]
        res = [0 for _ in range(size)]

        self.__helper(nums, 0, size - 1, temp, indexes, res)
        return res

    def __helper(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2

        # 计算一下左边
        self.__helper(nums, left, mid, temp, indexes, res)
        # 计算一下右边
        self.__helper(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序数组
        # [mid+1,right] 后有序数组

        # 先拷贝，再合并

        for i in range(left, right + 1):
            temp[i] = indexes[i]

        l = left
        r = mid + 1
        for i in range(left, right + 1):
            if l > mid:
                # l 用完，就拼命使用 r
                # [1,2,3,4] [5,6,7,8]
                indexes[i] = temp[r]
                r += 1
            elif r > right:
                # r 用完，就拼命使用 l
                # [6,7,8,9] [1,2,3,4]
                indexes[i] = temp[l]
                l += 1
                # 注意：此时前面剩下的数，比后面所有的数都大
                res[indexes[i]] += (right - mid)
            elif nums[temp[l]] <= nums[temp[r]]:
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[l]
                l += 1
                # 注意：
                res[indexes[i]] += (r - mid - 1)
            else:
                assert nums[temp[l]] > nums[temp[r]]
                # 上面两种情况只在其中一种统计就可以了
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[r]
                r += 1

Java 代码：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private int[] temp;
    private int[] counter;
    private int[] indexes;

    public List countSmaller(int[] nums) {
        List res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        temp = new int[len];
        counter = new int[len];
        indexes = new int[len];
        for (int i = 0; i < len; i++) {
            indexes[i] = i;
        }
        mergeAndCountSmaller(nums, 0, len - 1);
        for (int i = 0; i < len; i++) {
            res.add(counter[i]);
        }
        return res;
    }

    /**
     * 针对数组 nums 指定的区间 [l, r] 进行归并排序，在排序的过程中完成统计任务
     *
     * @param nums
     * @param l
     * @param r
     */
    private void mergeAndCountSmaller(int[] nums, int l, int r) {
        if (l == r) {
            // 数组只有一个元素的时候，没有比较，不统计
            return;
        }
        int mid = l + (r - l) / 2;
        mergeAndCountSmaller(nums, l, mid);
        mergeAndCountSmaller(nums, mid + 1, r);
        // 归并排序的优化，同样适用于该问题
        // 如果索引数组有序，就没有必要再继续计算了
        if (nums[indexes[mid]] > nums[indexes[mid + 1]]) {
            mergeOfTwoSortedArrAndCountSmaller(nums, l, mid, r);
        }
    }

    /**
     * [l, mid] 是排好序的
     * [mid + 1, r] 是排好序的
     *
     * @param nums
     * @param l
     * @param mid
     * @param r
     */
    private void mergeOfTwoSortedArrAndCountSmaller(int[] nums, int l, int mid, int r) {
        // 3,4  1,2
        for (int i = l; i <= r; i++) {
            temp[i] = indexes[i];
        }
        int i = l;
        int j = mid + 1;
        // 左边出列的时候，计数
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                indexes[k] = temp[j];
                j++;
            } else if (j > r) {
                indexes[k] = temp[i];
                i++;
                // 此时 j 用完了，[7,8,9 | 1,2,3]
                // 之前的数就和后面的区间长度构成逆序
                counter[indexes[k]] += (r - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) {
                indexes[k] = temp[i];
                i++;
                // 此时 [4,5, 6   | 1,2,3 10 12 13]
                //           mid          j
                counter[indexes[k]] += (j - mid - 1);
            } else {
                // nums[indexes[i]] > nums[indexes[j]] 构成逆序
                indexes[k] = temp[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 6, 1};
        Solution solution = new Solution();
        List countSmaller = solution.countSmaller(nums);
        System.out.println(countSmaller);
    }
}

复杂度分析：

• 时间复杂度：$O(N \log N)$，数组的元素个数是 $N$，递归执行分治法，时间复杂度是对数级别的，因此时间复杂度是 $O(N \log N)$。
• 空间复杂度：$O(N)$，需要 $3$ 个数组，一个索引数组，一个临时数组用于索引数组的归并，还有一个结果数组，它们的长度都是 $N$，故空间复杂度是 $O(N)$。

LeetCode 第 315 题：“计算右侧小于当前元素的个数”题解

题解地址：归并排序 + 索引数组。

说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。

传送门：计算右侧小于当前元素的个数。

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0]
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

归并排序 + 索引数组

归并排序 + 索引数组

如果有学习过一个数组的“逆序对”如何计算的朋友，对求解这道问题应该不陌生。

),),),),),),),),),),),),),),),),),),

求解 “逆序对” 的关键在于：当其中一个数字放进最终归并以后的有序数组中的时候，这个数字与之前看过的数字个数（或者是未看过的数字个数）可以直接统计出来，而不必一个一个数”。

“归并排序” 完成以后，原数组的 “逆序数” 也数出来了。

下面这句话很重要：

回到本题，本题让我们求 “在一个数组的某个元素的右边，比自己小的元素的个数”，因此，我们就 应该在 “前有序数组” 的元素出列的时候，数一数 “后有序数组” 已经出列了多少元素，因为这些已经出列的元素都比当前出列的元素要小（或者等于）。

发现问题

不过题目中要求我们要具体计算到元素级别。“归并排序” 完成以后，原始数组的位置就已经变化了，因此如何定位元素是关键。

想一想这一类问题是怎么解决的

一个元素在算法的执行过程中位置发生变化，我们还想定位它，这样的场景我们在 “最小索引堆” 中曾经学习过，从中得到启发，不妨也设置一个 “索引数组” 吧。使用 “索引数组” 的关键在于：

“原始数组” 不变，用于比较两个元素的大小，真正位置变换的是 “索引数组”。

下面我尝试解释一下 “索引数组” 的使用方法：

为了完成 “索引数组” 的归并，我们还需要一个 “索引数组” 长度的临时数组，把索引数组的值复制过去，比较完成以后，再赋值回 “索引数组”。具体请看下面的代码。

总结：

1、我们借助计算 “逆序数” 的思路完成本题，关键在于这里我们只能在 “前有序数组” 出列的时候计算逆序数；
如果题目让我们计算 “nums[i] 左侧小于 nums[i] 的元素的数量” 可以在 “后有序数组” 出列的时候计算逆序数；

2、体会 “索引数组” 这个使用技巧。

编码注意事项

一、可以复习一下 “归并排序” 的细节。

1、如果 “前有序数组” 和 “后有序数组” 直接合并的时候，就有序，就不必归并；

2、在 “归并” 的时候，全局使用一个临时存储数组，而不必每一个归并都新建临时的存储空间。

二、出列一个元素的时候，马上得到右边比自己小的元素的个数，是通过不同的指针之间的距离得到的。

在编码的时候，建议在草稿纸上写写画画，用具体的数值带进去，才能确保你计算的指针之间的距离正确。例如我写的 Python 代码 res[indexes[i]] += (right - mid) 和 res[indexes[i]] += (r - mid - 1) 这两句代码的计算，我就是在草稿纸上画出来的。

三、如果你写过 “逆序数” 的计算的代码，你就会发现，“逆序数” 的计算可以在 “前有序数组” 元素出列的时候计算逆序数，也可以在 “后有序数组” 元素出列的时候计算逆序数，你可以比较一下它们在编码时候的不同之处。

参考代码：

Python 代码：

class Solution:
    def countSmaller(self, nums):
        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        indexes = [i for i in range(size)]
        res = [0 for _ in range(size)]

        self.__helper(nums, 0, size - 1, temp, indexes, res)
        return res

    def __helper(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2

        # 计算一下左边
        self.__helper(nums, left, mid, temp, indexes, res)
        # 计算一下右边
        self.__helper(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序数组
        # [mid+1,right] 后有序数组

        # 先拷贝，再合并

        for i in range(left, right + 1):
            temp[i] = indexes[i]

        l = left
        r = mid + 1
        for i in range(left, right + 1):
            if l > mid:
                # l 用完，就拼命使用 r
                # [1,2,3,4] [5,6,7,8]
                indexes[i] = temp[r]
                r += 1
            elif r > right:
                # r 用完，就拼命使用 l
                # [6,7,8,9] [1,2,3,4]
                indexes[i] = temp[l]
                l += 1
                # 注意：此时前面剩下的数，比后面所有的数都大
                res[indexes[i]] += (right - mid)
            elif nums[temp[l]] <= nums[temp[r]]:
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[l]
                l += 1
                # 注意：
                res[indexes[i]] += (r - mid - 1)
            else:
                assert nums[temp[l]] > nums[temp[r]]
                # 上面两种情况只在其中一种统计就可以了
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[r]
                r += 1

Java 代码：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private int[] temp;
    private int[] counter;
    private int[] indexes;

    public List countSmaller(int[] nums) {
        List res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        temp = new int[len];
        counter = new int[len];
        indexes = new int[len];
        for (int i = 0; i < len; i++) {
            indexes[i] = i;
        }
        mergeAndCountSmaller(nums, 0, len - 1);
        for (int i = 0; i < len; i++) {
            res.add(counter[i]);
        }
        return res;
    }

    /**
     * 针对数组 nums 指定的区间 [l, r] 进行归并排序，在排序的过程中完成统计任务
     *
     * @param nums
     * @param l
     * @param r
     */
    private void mergeAndCountSmaller(int[] nums, int l, int r) {
        if (l == r) {
            // 数组只有一个元素的时候，没有比较，不统计
            return;
        }
        int mid = l + (r - l) / 2;
        mergeAndCountSmaller(nums, l, mid);
        mergeAndCountSmaller(nums, mid + 1, r);
        // 归并排序的优化，同样适用于该问题
        // 如果索引数组有序，就没有必要再继续计算了
        if (nums[indexes[mid]] > nums[indexes[mid + 1]]) {
            mergeOfTwoSortedArrAndCountSmaller(nums, l, mid, r);
        }
    }

    /**
     * [l, mid] 是排好序的
     * [mid + 1, r] 是排好序的
     *
     * @param nums
     * @param l
     * @param mid
     * @param r
     */
    private void mergeOfTwoSortedArrAndCountSmaller(int[] nums, int l, int mid, int r) {
        // 3,4  1,2
        for (int i = l; i <= r; i++) {
            temp[i] = indexes[i];
        }
        int i = l;
        int j = mid + 1;
        // 左边出列的时候，计数
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                indexes[k] = temp[j];
                j++;
            } else if (j > r) {
                indexes[k] = temp[i];
                i++;
                // 此时 j 用完了，[7,8,9 | 1,2,3]
                // 之前的数就和后面的区间长度构成逆序
                counter[indexes[k]] += (r - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) {
                indexes[k] = temp[i];
                i++;
                // 此时 [4,5, 6   | 1,2,3 10 12 13]
                //           mid          j
                counter[indexes[k]] += (j - mid - 1);
            } else {
                // nums[indexes[i]] > nums[indexes[j]] 构成逆序
                indexes[k] = temp[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 6, 1};
        Solution solution = new Solution();
        List countSmaller = solution.countSmaller(nums);
        System.out.println(countSmaller);
    }
}

复杂度分析：

• 时间复杂度：$O(N \log N)$，数组的元素个数是 $N$，递归执行分治法，时间复杂度是对数级别的，因此时间复杂度是 $O(N \log N)$。
• 空间复杂度：$O(N)$，需要 $3$ 个数组，一个索引数组，一个临时数组用于索引数组的归并，还有一个结果数组，它们的长度都是 $N$，故空间复杂度是 $O(N)$。

这道题还可以使用树状数组求解，这一点我们以后再介绍。