排序题目：计算右侧小于当前元素的个数

🕗 发布于 2024-10-10 19:58 排序

题目

标题和出处

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

出处：315. 计算右侧小于当前元素的个数

难度

8 级

题目描述

要求

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

示例

示例 1：

输入： $\texttt{nums = [5,2,6,1]}$
输出： $\texttt{[2,1,1,0]}$
解释：
$\texttt{5}$ 的右侧有 $\texttt{2}$ 个更小的元素（ $\texttt{2}$ 和 $\texttt{1}$ ）。
$\texttt{2}$ 的右侧有 $\texttt{1}$ 个更小的元素（ $\texttt{1}$ ）。
$\texttt{6}$ 的右侧有 $\texttt{1}$ 个更小的元素（ $\texttt{1}$ ）。
$\texttt{1}$ 的右侧有 $\texttt{0}$ 个更小的元素。

示例 2：

输入： $\texttt{nums = [-1]}$
输出： $\texttt{[0]}$

示例 3：

输入： $\texttt{nums = [-1,-1]}$
输出： $\texttt{[0,0]}$

数据范围

$\texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5}$
$\texttt{-10}^\texttt{4} \le \texttt{nums[i]} \le \texttt{10}^\texttt{4}$

前言

定义「逆序对」的概念如下：对于下标 $i$ 和 $j$ ，如果 $i < j$ 且 $\textit{nums}[i] > \textit{nums}[j]$ ，则下标对 $(i, j)$ 是一个逆序对。

这道题要求计算数组 $\textit{nums}$ 中的每个元素右侧小于当前元素的个数，实质是计算每个元素右侧的元素中与当前元素形成逆序对的元素个数。

对于长度为 $n$ 的数组，最朴素的计算逆序对的数量的方法是对于每个元素遍历其右边的元素并统计可以形成逆序对的元素个数，每个元素需要 $O (n)$ 的时间计算逆序对的个数，总时间复杂度是 $O(n^2)$ 。由于数组 $\textit{nums}$ 的长度最大为 $10^5$ ，因此 $O(n^2)$ 的时间复杂度过高，必须使用时间复杂度更低的方法。

以下介绍三种时间复杂度 $\log n)$ 的计算逆序对数量的方法，分别是归并排序、线段树和树状数组。

解法一

思路和算法

由于逆序对和排序相关，因此可以使用排序的思想计算逆序对的数量。归并排序的过程中，每次将两个升序子数组合并，合并的过程中即可发现这两个升序子数组中的逆序对。因此可以在归并排序的过程中计算每个元素右侧的元素中与当前元素形成逆序对的元素个数。

考虑下标范围 $[\textit{low}, \textit{high}]$ 的子数组的归并排序过程。当 $\textit{low} \ge \textit{high}$ 时，子数组的长度是 $0$ 或 $1$ ，此时子数组已经符合升序。当 $\textit{low} < \textit{high}$ 时，子数组的长度大于等于 $2$ ，归并排序的过程为将子数组分成两个更短的子数组，两个更短的子数组排序之后合并，具体过程如下。

取 $\textit{low}$ 和 $\textit{high}$ 的平均值 $\textit{mid}$ ，将下标范围 $[\textit{low}, \textit{high}]$ 的子数组分成下标范围 $[\textit{low}, \textit{mid}]$ 和下标范围 $[\textit{mid} + 1, \textit{high}]$ 的两个子数组。
将下标范围 $[\textit{low}, \textit{mid}]$ 和下标范围 $[\textit{mid} + 1, \textit{high}]$ 的两个子数组分别排序，得到两个升序子数组。
用 $i$ 和 $j$ 分别表示下标范围 $[\textit{low}, \textit{mid}]$ 和下标范围 $[\textit{mid} + 1, \textit{high}]$ 的两个升序子数组中的待合并元素下标，初始时 $\textit{low}$ ， $\textit{mid} + 1$ 。当 $\le \textit{mid}$ 且 $\le \textit{high}$ 时，按照如下操作合并两个子数组，合并过程中需要保持排序的稳定性。
- 如果 $\textit{nums}[i] \le \textit{nums}[j]$ ，则将 $\textit{nums}[i]$ 添加到合并后的结果中，然后将 $i$ 加 $1$ 。
- 如果 $\textit{nums}[i] > \textit{nums}[j]$ ，则将 $\textit{nums}[j]$ 添加到合并后的结果中，然后将 $j$ 加 $1$ 。
当其中一个升序子数组的元素全部合并结束之后，将另一个升序子数组的元素依次添加到合并后的结果中。

由于合并过程保持排序的稳定性，因此当 $\textit{nums}[i] \le \textit{nums}[j]$ 或者 $\textit{high} + 1$ 时，一定有 $\textit{nums}[i] > \textit{nums}[j - 1]$ （如果 $\textit{high} + 1$ ，则有 $\textit{high}$ ），否则 $\textit{nums}[i] = \textit{nums}[j - 1]$ ，在合并 $\textit{nums}[i]$ 之前合并 $\textit{nums}[j - 1]$ 与归并排序的稳定性矛盾。因此对于任意 $\textit{mid} + 1 \le k \le j - 1$ 都有 $\textit{nums}[i] > \textit{nums}[k]$ ，即在下标范围 $[\textit{mid} + 1, \textit{high}]$ 的升序子数组中有 $\textit{mid} - 1$ 个数小于 $\textit{nums}[i]$ ，将 $\textit{mid} - 1$ 加到 $\textit{nums}[i]$ 对应的计数中。

为了记录每个元素右侧小于当前元素的个数，需要维护下标数组和计数数组，在归并排序计算逆序对的过程中同时对原数组和下标数组执行归并操作，确保原数组和下标数组中的每个元素分别对应。当更新一个元素对应的计数时，从下标数组得到该元素的下标，更新计数数组中该下标处的计数。

当整个数组排序结束时，计数数组即为每个元素右侧小于当前元素的个数。

由于计算每个元素的逆序对数量以及合并两个升序子数组都需要遍历两个升序子数组，因此计算每个元素的逆序对数量并没有提升总时间复杂度，总时间复杂度和原始归并排序一样是 $\log n)$ 。

归并排序可以使用自顶向下的方式递归实现，也可以使用自底向上的方式迭代实现。对于同一个数组，使用自顶向下和自底向上两种方式实现的中间过程可能有所区别，但是都能得到正确的结果。

代码

以下代码为归并排序的自顶向下实现。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int length = nums.length;
        int[] indices = new int[length];
        for (int i = 0; i < length; i++) {
            indices[i] = i;
        }
        List<Integer> counts = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            counts.add(0);
        }
        mergeSortAndCount(nums, indices, counts, 0, length - 1);
        return counts;
    }

    public void mergeSortAndCount(int[] nums, int[] indices, List<Integer> counts, int low, int high) {
        if (low >= high) {
            return;
        }
        int mid = low + (high - low) / 2;
        mergeSortAndCount(nums, indices, counts, low, mid);
        mergeSortAndCount(nums, indices, counts, mid + 1, high);
        merge(nums, indices, counts, low, mid, high);
    }

    public void merge(int[] nums, int[] indices, List<Integer> counts, int low, int mid, int high) {
        int currLength = high - low + 1;
        int[] tempNums = new int[currLength];
        int[] tempIndices = new int[currLength];
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                tempNums[k] = nums[i];
                tempIndices[k] = indices[i];
                counts.set(indices[i], counts.get(indices[i]) + (j - mid - 1));
                i++;
            } else {
                tempNums[k] = nums[j];
                tempIndices[k] = indices[j];
                j++;
            }
            k++;
        }
        while (i <= mid) {
            tempNums[k] = nums[i];
            tempIndices[k] = indices[i];
            counts.set(indices[i], counts.get(indices[i]) + (j - mid - 1));
            i++;
            k++;
        }
        while (j <= high) {
            tempNums[k] = nums[j];
            tempIndices[k] = indices[j];
            j++;
            k++;
        }
        System.arraycopy(tempNums, 0, nums, low, currLength);
        System.arraycopy(tempIndices, 0, indices, low, currLength);
    }
}

以下代码为归并排序的自底向上实现。

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        int length = nums.length;
        int[] indices = new int[length];
        for (int i = 0; i < length; i++) {
            indices[i] = i;
        }
        List<Integer> counts = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            counts.add(0);
        }
        for (int halfLength = 1, currLength = 2; halfLength < length; halfLength *= 2, currLength *= 2) {
            for (int low = 0; low < length - halfLength; low += currLength) {
                int mid = low + halfLength - 1;
                int high = Math.min(low + currLength - 1, length - 1);
                merge(nums, indices, counts, low, mid, high);
            }
        }
        return counts;
    }

    public void merge(int[] nums, int[] indices, List<Integer> counts, int low, int mid, int high) {
        int currLength = high - low + 1;
        int[] tempNums = new int[currLength];
        int[] tempIndices = new int[currLength];
        int i = low, j = mid + 1, k = 0;
        while (i <= mid && j <= high) {
            if (nums[i] <= nums[j]) {
                tempNums[k] = nums[i];
                tempIndices[k] = indices[i];
                counts.set(indices[i], counts.get(indices[i]) + (j - mid - 1));
                i++;
            } else {
                tempNums[k] = nums[j];
                tempIndices[k] = indices[j];
                j++;
            }
            k++;
        }
        while (i <= mid) {
            tempNums[k] = nums[i];
            tempIndices[k] = indices[i];
            counts.set(indices[i], counts.get(indices[i]) + (j - mid - 1));
            i++;
            k++;
        }
        while (j <= high) {
            tempNums[k] = nums[j];
            tempIndices[k] = indices[j];
            j++;
            k++;
        }
        System.arraycopy(tempNums, 0, nums, low, currLength);
        System.arraycopy(tempIndices, 0, indices, low, currLength);
    }
}

复杂度分析

时间复杂度： $\log n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。归并排序的时间复杂度是 $\log n)$ 。
空间复杂度： $O (n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。下标数组需要 $O (n)$ 的空间，自顶向下实现时需要递归调用栈的空间是 $O(\log n)$ ，自底向上实现时可以省略递归调用栈的空间。无论是自顶向下实现还是自底向上实现，归并过程需要 $O (n)$ 的辅助空间。

解法二

预备知识

该解法涉及到线段树。线段树是一种二叉搜索树，将一个区间划分成两个更短的区间。线段树中的每个叶结点都是长度为 $1$ 的区间，称为单元区间。

线段树支持区间的快速查询和修改。对于长度为 $n$ 的区间，使用线段树查询特定子区间的元素个数以及修改特定子区间内的元素个数的时间是 $O(\log n)$ 。

有时，为了降低线段树的空间复杂度，需要使用离散化。

思路和算法

对于长度为 $n$ 的数组，其中不同元素的个数最多有 $n$ 个。由于计算逆序对数量只需要考虑元素的相对大小，因此可以使用离散化将区间长度限制在 $n$ 以内。离散化的方法是计算数组 $\textit{nums}$ 中的每个元素的名次，计算名次的方法是：新建数组 $\textit{sorted}$ 并将数组 $\textit{nums}$ 中的所有元素复制到数组 $\textit{sorted}$ 中，然后对数组 $\textit{sorted}$ 排序，排序之后， $\textit{sorted}[i]$ 的名次为 $i$ ，如果 $i > 0$ 且 $\textit{sorted}[i] = \textit{sorted}[i - 1]$ 则 $\textit{sorted}[i]$ 的名次与 $\textit{sorted}[i - 1]$ 的名次相同。每个元素的名次都在范围 $[0, n - 1]$ 中，表示数组中的小于该元素的元素个数。

由于这道题要求计算每个元素右侧的元素中与当前元素形成逆序对的元素个数，因此遍历数组 $\textit{nums}$ 的过程中需要确保每个元素右侧的元素已经遍历过，需要从右到左遍历数组 $\textit{nums}$ 计算逆序对的数量。

创建线段树，用于存储数组 $\textit{nums}$ 中的每个元素的名次。从右到遍历数组 $\textit{nums}$ ，对于每个元素 $\textit{num}$ ，其右侧的元素已经遍历过，其右侧的元素中的每个小于 $\textit{num}$ 的元素都与 $\textit{num}$ 组成一个逆序对，因此得到 $\textit{num}$ 的名次 $\textit{rank}$ ，计算线段树的子区间 $\textit{rank} - 1]$ 中的元素个数，该元素个数即为当前元素 $\textit{num}$ 元素右侧小于 $\textit{num}$ 的元素个数。得到当前元素右侧小于当前元素的个数之后，将 $\textit{rank}$ 添加到线段树中，继续向左遍历元素并计算每个元素右侧小于当前元素的个数。遍历结束之后，即可得到数组 $\textit{nums}$ 中的每个元素右侧小于当前元素的个数。

代码

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> counts = new ArrayList<Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            counts.add(0);
        }
        Map<Integer, Integer> ranks = getRanks(nums);
        SegmentTree st = new SegmentTree(length);
        for (int i = length - 1; i >= 0; i--) {
            int rank = ranks.get(nums[i]);
            counts.set(i, st.getCount(0, rank - 1));
            st.add(rank);
        }
        return counts;
    }

    public Map<Integer, Integer> getRanks(int[] nums) {
        int length = nums.length;
        int[] sorted = new int[length];
        System.arraycopy(nums, 0, sorted, 0, length);
        Arrays.sort(sorted);
        Map<Integer, Integer> ranks = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
            int num = sorted[i];
            if (i == 0 || num > sorted[i - 1]) {
                ranks.put(num, i);
            }
        }
        return ranks;
    }
}

class SegmentTree {
    int length;
    int[] tree;

    public SegmentTree(int length) {
        this.length = length;
        this.tree = new int[length * 4];
    }

    public int getCount(int start, int end) {
        return getCount(start, end, 0, 0, length - 1);
    }

    public void add(int rank) {
        add(rank, 0, 0, length - 1);
    }

    private int getCount(int rangeStart, int rangeEnd, int index, int treeStart, int treeEnd) {
        if (rangeStart > rangeEnd) {
            return 0;
        }
        if (rangeStart == treeStart && rangeEnd == treeEnd) {
            return tree[index];
        }
        int mid = treeStart + (treeEnd - treeStart) / 2;
        if (rangeEnd <= mid) {
            return getCount(rangeStart, rangeEnd, index * 2 + 1, treeStart, mid);
        } else if (rangeStart > mid) {
            return getCount(rangeStart, rangeEnd, index * 2 + 2, mid + 1, treeEnd);
        } else {
            return getCount(rangeStart, mid, index * 2 + 1, treeStart, mid) + getCount(mid + 1, rangeEnd, index * 2 + 2, mid + 1, treeEnd);
        }
    }

    private void add(int rank, int index, int start, int end) {
        if (start == end) {
            tree[index]++;
            return;
        }
        int mid = start + (end - start) / 2;
        if (rank <= mid) {
            add(rank, index * 2 + 1, start, mid);
        } else {
            add(rank, index * 2 + 2, mid + 1, end);
        }
        tree[index] = tree[index * 2 + 1] + tree[index * 2 + 2];
    }
}

复杂度分析

时间复杂度： $\log n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。每个元素在线段树中的查询和更新操作都需要 $O(\log n)$ 的时间，时间复杂度是 $\log n)$ 。
空间复杂度： $O (n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。创建线段树需要 $O (n)$ 的空间。

解法三

预备知识

该解法涉及到树状数组。树状数组也称二叉索引树，由 Peter M. Fenwick 发明，因此又称 Fenwick 树。树状数组支持快速计算数组的前缀和与区间和，以及快速修改。对于长度为 $n$ 的区间，使用树状数组查询特定子区间的区间和以及修改特定子区间内的元素值的时间是 $O(\log n)$ 。

有时，为了降低树状数组的空间复杂度，需要使用离散化。

思路和算法

计算每个元素右侧小于当前元素的个数也可以使用树状数组实现。

首先使用离散化将区间长度限制在 $n$ 以内，然后创建树状数组，用于存储数组 $\textit{nums}$ 中的每个元素的名次。从右到左遍历数组 $\textit{nums}$ ，对于每个元素 $\textit{num}$ ，得到 $\textit{num}$ 的名次 $\textit{rank}$ ，计算树状数组的子区间 $\textit{rank} + 1]$ 中的元素个数，该元素个数即为即为当前元素 $\textit{num}$ 元素右侧小于 $\textit{num}$ 的元素个数。得到当前元素右侧小于当前元素的个数之后，将 $\textit{rank}$ 添加到树状数组中，继续向左遍历元素并计算每个元素右侧小于当前元素的个数。遍历结束之后，即可得到数组 $\textit{nums}$ 中的每个元素右侧小于当前元素的个数。

代码

class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> counts = new ArrayList<Integer>();
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            counts.add(0);
        }
        Map<Integer, Integer> ranks = getRanks(nums);
        BinaryIndexedTree bit = new BinaryIndexedTree(length);
        for (int i = length - 1; i >= 0; i--) {
            int rank = ranks.get(nums[i]);
            counts.set(i, bit.getCount(0, rank - 1));
            bit.add(rank);
        }
        return counts;
    }

    public Map<Integer, Integer> getRanks(int[] nums) {
        int length = nums.length;
        int[] sorted = new int[length];
        System.arraycopy(nums, 0, sorted, 0, length);
        Arrays.sort(sorted);
        Map<Integer, Integer> ranks = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
            int num = sorted[i];
            if (i == 0 || num > sorted[i - 1]) {
                ranks.put(num, i);
            }
        }
        return ranks;
    }
}

class BinaryIndexedTree {
    int length;
    int[] tree;

    public BinaryIndexedTree(int length) {
        this.length = length;
        this.tree = new int[length + 1];
    }

    public int getCount(int start, int end) {
        return getPrefixSum(end + 1) - getPrefixSum(start);
    }

    public void add(int index) {
        index++;
        while (index <= length) {
            tree[index]++;
            index += lowbit(index);
        }
    }

    private int getPrefixSum(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= lowbit(index);
        }
        return sum;
    }

    private static int lowbit(int x) {
        return x & (-x);
    }
}

复杂度分析

时间复杂度： $\log n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。每个元素在树状数组中的查询和更新操作都需要 $O(\log n)$ 的时间，时间复杂度是 $\log n)$ 。
空间复杂度： $O (n)$ ，其中 $n$ 是数组 $\textit{nums}$ 的长度。创建树状数组需要 $O (n)$ 的空间。

原文地址：https://blog.csdn.net/stormsunshine/article/details/125584413

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：全栈开发笔记
下一篇：浙江嘉兴晋亿实业5MW分布式储能项目中的应用

SQL自学：什么是子查询，如何使用它们
子查询是一个嵌套在另一个 SQL 查询（通常是 SELECT、INSERT、UPDATE 或 DELETE 语句）中的查询。它的结果被用作外部查询的一部分，以进一步筛选、聚合或连接数据。子查询可以返回
阅读更多2024-10-10
Docker容器不断重启问题
在compose配置文件中，卷标app会被自动重命名为node_app，而恰好上次使用的卷标没有清理，冲突了。查看docker已经存在的卷标。
阅读更多2024-10-10
Linux——cp-mv-rm命令
复制文件 cp test01.txt test02.txt。删除文件 rm test.txt。删除文件夹（目录 rm。
阅读更多2024-10-10
【Linux第一弹】- 基本指令
Linux基本指令
阅读更多2024-10-10
Android实现RecyclerView宽度变化动画
实现思路就是定义一个属性动画，在动画监听器中不断修改RecyclerView的宽度。
阅读更多2024-10-10
猜Follow邀请码
猜邀请码把zero*width替换成可能的字符(包含 a-z, A-Z 和 0-9),生成所有可能。
阅读更多2024-10-10
Python测试框架--Allure
AllureAllure是由Qameta Software团队开源的一款旨在于解决让每个人能更容易生成并更简洁阅读的测试报告框架。它支持大多数的测试框架，如：Pytest、TestNG等，简单易用便于
阅读更多2024-10-10
获取股票期货历史高频分钟以及macd量化
例如，如果在日线图上MACD显示买入信号，而周线图上MACD显示卖出信号，则可能需要更谨慎地对待这个买入信号。MACD线作为技术分析中的一个常用工具，确实存在一些高级使用技巧，这些技巧可以帮助投资者更
阅读更多2024-10-10
Flash 闪存技术基础与 SD NAND Flash 产品测试解析
本篇除了对flash闪存进行简单介绍外，另给读者推荐一种我本人也在用的小容量闪存。自带坏块管理的SD NAND Flash（贴片式TF卡），尺寸小巧，简单易用，兼容性强，稳定可靠，标准SDIO接口，兼
阅读更多2024-10-10
哪种隔音方式最好？小户型如何隔音？
在选择隔音板时，一定要看CMA（中国计量认证）和CNAS（中国合格评定国家认可委员会）的检测报告，除了此法，没有其他任何办法辨别它的性能，只能等施工结束后才知晓它的隔音效果。隔音毡是一种以橡胶、塑胶等
阅读更多2024-10-10

排序题目：计算右侧小于当前元素的个数

文章目录

题目

标题和出处

难度

题目描述

要求

示例

数据范围

前言

解法一

思路和算法

代码

复杂度分析

解法二

预备知识

思路和算法

代码

复杂度分析

解法三

预备知识

思路和算法

代码

复杂度分析

相关文章