【算法】分治:归并排序之 315.计算右侧小于当前元素的个数(hard)

时间:2024-09-30 07:24:18

hard太难了啦,大家还是酌情做题,不要浪费太多时间。

相关题目:LCR 170. 交易逆序对的总数 - 力扣(LeetCode)

目录

1、题目链接

2、题目介绍

3、解法

4、代码 


1、题目链接

315. 计算右侧小于当前元素的个数 - 力扣(LeetCode)

2、题目介绍

给你一个整数数组 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

3、解法

题解 - 力扣(LeetCode)

在这里推荐大家阅读上面这篇题解~

大概能清楚大部分思路。

具体步骤如下:

  1. 初始化:创建一个与原数组 nums 大小相同的 index 数组,用于存储 nums 中每个元素的原始索引。

    1. 这是因为归并排序会打乱元素的顺序,但我们需要保留元素的原始位置来正确计算每个位置的结果。同时,创建两个辅助数组 index_temp 和 ret,其中 index_temp 用于归并过程中的临时索引存储,ret 用于存储最终结果即每个元素右侧小于它的元素数量。

  2. 归并排序:对 nums 数组进行归并排序,但在排序过程中,我们并不直接对 nums 进行操作,而是对 index 数组进行操作。这样做的原因是,我们可以通过 index 数组间接地比较 nums 中的元素,并保留元素的原始位置信息。在归并的过程中,每当我们将一个来自左子数组的索引放入 index_temp 时,我们就知道它右侧(在 nums 中)有多少来自右子数组的元素小于它(这些元素已经被排序并放在其右侧),从而可以更新 ret 数组中对应位置的值。

  3. 计算并更新结果:在归并的过程中,我们使用两个指针 i 和 j 分别指向左子数组和右子数组的当前索引,并通过比较 nums[index[i]] 和 nums[index[j]] 的大小来决定将哪个索引放入 index_temp

    1. 如果 nums[index[i]] 小于或等于 nums[index[j]],那么我们可以安全地将 index[i] 放入 index_temp,并增加 ret[index[i]] 的值,增加的数量是 j - mid - 1(即当前右子数组中还未处理的、且小于 nums[index[i]] 的元素数量)。

  4. 返回结果:归并排序完成后,ret 数组中存储的就是每个元素右侧小于它的元素数量,直接返回 ret 即可。

这种方法的时间复杂度是 O(n log n),因为归并排序的时间复杂度是 O(n log n),而我们在归并的过程中只进行了线性的额外操作。空间复杂度也是 O(n),因为我们使用了与输入数组大小相同的额外空间来存储索引、临时索引和结果。

4、代码 

class Solution {
public:
    vector<int> index_temp;
    vector<int> ret;
    void mergeSort(vector<int>& nums, vector<int>& index, int l, int r) {
        if (l >= r) return;
        int mid = (l + r) >> 1;
        mergeSort(nums, index, l, mid);
        mergeSort(nums, index, mid + 1, r);
        if (nums[index[mid]] <= nums[index[mid + 1]]) return;
        int i = l, j = mid + 1, k = l;
        while (i <= mid && j <= r) {
            if (nums[index[i]] <= nums[index[j]]) {
                ret[index[i]] += j - mid - 1;
                index_temp[k++] = index[i++];
            }
            else index_temp[k++] = index[j++];
        }
        while (i <= mid) {
            ret[index[i]] += j - mid - 1;
            index_temp[k++] = index[i++];
        }
        while (j <= r) index_temp[k++] = index[j++];
        for (i = l; i <= r; i++) index[i] = index_temp[i];
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        index_temp.resize(n);
        ret.resize(n);
        vector<int> index(n);
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        mergeSort(nums, index, 0, n - 1);
        return ret;
    }
};

????感谢阅读!????