计算右侧小于当前元素的个数

描述

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

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素
示例 2：

输入：nums = [-1]
输出：[0]
示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

C++代码

这道题给定了一个数组，让我们计算每个数字右边所有小于这个数字的个数，目测不能用 brute force，OJ 肯定不答应，那么为了提高运算效率，首先可以使用用二分搜索法，思路是将给定数组从最后一个开始，用二分法插入到一个新的数组，这样新数组就是有序的，那么此时该数字在新数组中的坐标就是原数组中其右边所有较小数字的个数，参见代码如下：

解法一:

// Binary Search
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size()); // res用于保存结果, t是用于插入排序的新数组
        for (int i = nums.size() - 1; i >= 0; --i) {
            int left = 0, right = t.size();
            while (left < right) {
                int mid = left + (right - left) / 2;
                if (t[mid] >= nums[i]) right = mid;
                else left = mid + 1;
            }
            res[i] = right;
            t.insert(t.begin() + right, nums[i]);
        }
        return res;
    }
};


class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size(), 0); // 初始化结果数组
        vector<int> sorted_nums; // 初始化排序后的数组
        for (int i = nums.size() - 1; i >= 0; i--) { // 从后往前遍历原数组
            int left = 0, right = sorted_nums.size(); // 初始化左右指针
            while (left < right) { // 二分查找插入位置
                int mid = left + (right - left) / 2;
                if (sorted_nums[mid] >= nums[i]) {
                    right = mid;
                } else {
                    left = mid + 1;
                }
            }
            res[i] = right; // 记录当前元素在排序后数组中的位置
            sorted_nums.insert(sorted_nums.begin() + right, nums[i]); // 将当前元素插入排序后数组
        }
        return res;
    }
};

上面使用二分搜索法是一种插入排序的做法，我们还可以用 C++ 中的 STL 的一些自带的函数，比如求距离 distance，或是求第一个不小于当前数字的函数 lower_bound()，这里利用这两个函数代替了上一种方法中的二分搜索的部分，两种方法的核心思想都是相同的，构造有序数组，找出新加进来的数组在有序数组中对应的位置存入结果中即可，参见代码如下：

解法二：

// Insert Sort
class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> t, res(nums.size());
        for (int i = nums.size() - 1; i >= 0; --i) {
            int d = distance(t.begin(), lower_bound(t.begin(), t.end(), nums[i]));
            res[i] = d;
            t.insert(t.begin() + d, nums[i]);
        }
        return res;
    }
};

再来看一种利用二分搜索树来解的方法，构造一棵二分搜索树，稍有不同的地方是需要加一个变量 smaller 来记录比当前结点值小的所有结点的个数，每插入一个结点，会判断其和根结点的大小，如果新的结点值小于根结点值，则其会插入到左子树中，此时要增加根结点的 smaller，并继续递归调用左子结点的 insert。如果结点值大于根结点值，则需要递归调用右子结点的 insert 并加上根结点的 smaller，并加1，参见代码如下：

解法三：

// Binary Search Tree
class Solution {
public:
    struct Node {
        int val, smaller;
        Node *left, *right;
        Node(int v, int s) : val(v), smaller(s), left(NULL), right(NULL) {}
    };
    int insert(Node*& root, int val) {
        if (!root) return (root = new Node(val, 0)), 0;
        if (root->val > val) return root->smaller++, insert(root->left, val);
        return insert(root->right, val) + root->smaller + (root->val < val ? 1 : 0);
    }
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size());
        Node *root = NULL;
        for (int i = nums.size() - 1; i >= 0; --i) {
            res[i] = insert(root, nums[i]);
        }
        return res;
    }
};

解法四：归并排序

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size(), 0);
        // 第一个int是原始数组中的值，第二个int是该值在原始数组中的index
        vector<pair<int, int>> v;
        for (int i = 0; i < nums.size(); i++) {
            v.push_back(make_pair(nums[i], i));
        }
        mergeSort(v, res);
        return res;
    }

    void mergeSort(vector<pair<int, int>>& v, vector<int>& res) {
        if (v.size() <= 1) {
            return;
        }
        int mid = v.size() / 2;
        // 分为了两部分, [a,mid)和[mid,b)
        vector<pair<int, int>> left(v.begin(), v.begin() + mid);
        vector<pair<int, int>> right(v.begin() + mid, v.end());
        mergeSort(left, res);
        mergeSort(right, res);
        merge(v, left, right, res);
    }

    void merge(vector<pair<int, int>>& v, vector<pair<int, int>>& left, vector<pair<int, int>>& right, vector<int>& res) {
        int i = 0, j = 0;
        while (i < left.size() && j < right.size()) {
            if (left[i].first <= right[j].first) { // 进行值比较, 谁值小谁前进嘛
                // 将左半部分中的元素放到结果数组中
                //并将左半部分中的元素对应的逆序对个数加上右半部分中已经处理过的元素个数j
                v[i + j] = left[i];
                res[left[i].second] += j;
                i++;
            } else {
                // 如果右半部分中的元素小于左半部分中的元素，将右半部分中的元素放到结果数组中
                //并将指针j向右移动
                v[i + j] = right[j];
                j++;
            }
        }
        // 如果左半部分中还有元素没有处理完，将这些元素放到结果数组中
        //并将它们对应的逆序对个数加上右半部分中已经处理过的元素个数j
        while (i < left.size()) {
            v[i + j] = left[i];
            res[left[i].second] += j;
            i++;
        }
        // 如果右半部分中还有元素没有处理完，将这些元素放到结果数组中
        while (j < right.size()) {
            v[i + j] = right[j];
            j++;
        }
    }
};

这个解决方案的主要思想是使用归并排序的变体来解决问题。我们需要对原始数组进行排序，并在排序过程中计算每个元素后面有多少个比它小的元素。具体来说，我们首先将原始数组转换为一个pair数组，其中第一个元素是原始数组中的值，第二个元素是该值在原始数组中的索引。然后我们对这个pair数组进行归并排序。在归并的过程中，我们需要维护一个计数器来计算每个元素后面有多少个比它小的元素。具体来说，当我们将一个左边的子数组中的元素归并到右边的子数组中时，我们需要将计数器增加右边子数组中比当前元素小的元素的数量。这个数量可以通过 mid + 1 - j 来计算，其中 j 是右边子数组中当前比较的元素的索引。

最后，我们将排序后的pair数组转换回原始数组，并返回计数器数组。