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

📖 文章摘要

本文详细解析LeetCode第315题“计算右侧小于当前元素的个数”，这是一道数组和二分查找的问题。文章提供了基于归并排序和树状数组两种解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要深入理解数组处理和高级数据结构的程序员。

核心知识点： 归并排序、树状数组、二分查找
难度等级： 困难
推荐人群： 具有一定算法基础，想要提升数组处理能力的程序员

题目描述

给你一个整数数组 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 <= 10^5
-10^4 <= nums[i] <= 10^4

解题思路

方法一：归并排序

这道题可以使用归并排序的思想来解决。在归并排序的过程中，我们可以统计每个元素右侧小于它的元素个数。

关键点：

使用归并排序的过程来统计逆序对
维护原始索引以记录每个元素的位置
在合并过程中统计右侧小于当前元素的个数

具体步骤：

创建一个索引数组，记录每个元素的原始位置
对索引数组进行归并排序
在归并过程中，统计右侧小于当前元素的个数
最终返回统计结果

时间复杂度：O(nlogn) 空间复杂度：O(n)

方法二：树状数组

树状数组是一种高效的数据结构，可以用来处理区间查询和单点更新。

关键点：

将数组离散化，压缩值域
使用树状数组维护前缀和
从右向左遍历数组，统计小于当前元素的个数

具体步骤：

对数组进行离散化处理
构建树状数组
从右向左遍历原数组
对于每个元素，查询树状数组中小于当前元素的个数
更新树状数组

时间复杂度：O(nlogn) 空间复杂度：O(n)

图解思路

归并排序过程分析表

步骤	操作	数组状态	统计结果
初始状态	-	[5,2,6,1]	[0,0,0,0]
分割	分成左右两部分	[5,2] [6,1]	[0,0,0,0]
递归处理	处理左右子数组	[2,5] [1,6]	[1,0,1,0]
合并	合并有序子数组	[1,2,5,6]	[2,1,1,0]

树状数组状态分析表

操作	当前元素	树状数组状态	统计结果
初始化	-	[0,0,0,0]	[0,0,0,0]
处理1	1	[1,1,0,0]	[?,?,?,0]
处理6	6	[1,1,1,0]	[?,?,1,0]
处理2	2	[1,2,1,0]	[?,1,1,0]
处理5	5	[1,2,2,0]	[2,1,1,0]

代码实现

C# 实现

public class Solution {
    private int[] count;
    private int[] temp;
    private int[] tempIndex;
    private int[] index;
    
    public IList<int> CountSmaller(int[] nums) {
        int n = nums.Length;
        count = new int[n];
        temp = new int[n];
        tempIndex = new int[n];
        index = new int[n];
        
        // 初始化索引数组
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        
        // 归并排序
        MergeSort(nums, 0, n - 1);
        
        return count.ToList();
    }
    
    private void MergeSort(int[] nums, int left, int right) {
        if (left >= right) return;
        
        int mid = (left + right) / 2;
        MergeSort(nums, left, mid);
        MergeSort(nums, mid + 1, right);
        Merge(nums, left, mid, right);
    }
    
    private void Merge(int[] nums, int left, int mid, int right) {
        int i = left, j = mid + 1;
        int p = left;
        
        // 复制数组
        for (int k = left; k <= right; k++) {
            temp[k] = nums[k];
            tempIndex[k] = index[k];
        }
        
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                nums[p] = temp[i];
                index[p] = tempIndex[i];
                count[tempIndex[i]] += j - (mid + 1);
                i++;
            } else {
                nums[p] = temp[j];
                index[p] = tempIndex[j];
                j++;
            }
            p++;
        }
        
        while (i <= mid) {
            nums[p] = temp[i];
            index[p] = tempIndex[i];
            count[tempIndex[i]] += right - mid;
            i++;
            p++;
        }
        
        while (j <= right) {
            nums[p] = temp[j];
            index[p] = tempIndex[j];
            j++;
            p++;
        }
    }
}

Python 实现

class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        def update(index: int, value: int, tree: List[int], size: int) -> None:
            while index < size:
                tree[index] += value
                index += index & (-index)
                
        def query(index: int, tree: List[int]) -> int:
            result = 0
            while index > 0:
                result += tree[index]
                index -= index & (-index)
            return result
        
        # 离散化
        sorted_nums = sorted(set(nums))
        ranks = {num: i + 1 for i, num in enumerate(sorted_nums)}
        
        n = len(nums)
        result = [0] * n
        tree = [0] * (len(ranks) + 1)
        
        # 从右向左遍历
        for i in range(n - 1, -1, -1):
            rank = ranks[nums[i]]
            result[i] = query(rank - 1, tree)
            update(rank, 1, tree, len(ranks) + 1)
            
        return result

C++ 实现

class Solution {
private:
    vector<int> count;
    vector<int> temp;
    vector<int> tempIndex;
    vector<int> index;
    
    void mergeSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        
        int mid = (left + right) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    void merge(vector<int>& nums, int left, int mid, int right) {
        int i = left, j = mid + 1;
        int p = left;
        
        for (int k = left; k <= right; k++) {
            temp[k] = nums[k];
            tempIndex[k] = index[k];
        }
        
        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                nums[p] = temp[i];
                index[p] = tempIndex[i];
                count[tempIndex[i]] += j - (mid + 1);
                i++;
            } else {
                nums[p] = temp[j];
                index[p] = tempIndex[j];
                j++;
            }
            p++;
        }
        
        while (i <= mid) {
            nums[p] = temp[i];
            index[p] = tempIndex[i];
            count[tempIndex[i]] += right - mid;
            i++;
            p++;
        }
        
        while (j <= right) {
            nums[p] = temp[j];
            index[p] = tempIndex[j];
            j++;
            p++;
        }
    }
    
public:
    vector<int> countSmaller(vector<int>& nums) {
        int n = nums.size();
        count.resize(n);
        temp.resize(n);
        tempIndex.resize(n);
        index.resize(n);
        
        for (int i = 0; i < n; i++) {
            index[i] = i;
        }
        
        mergeSort(nums, 0, n - 1);
        
        return count;
    }
};

执行结果

C# 实现

执行用时：248 ms
内存消耗：45.8 MB

Python 实现

执行用时：1876 ms
内存消耗：35.2 MB

C++ 实现

执行用时：156 ms
内存消耗：33.6 MB

性能对比

语言	执行用时	内存消耗	特点
C#	248 ms	45.8 MB	实现简洁，性能适中
Python	1876 ms	35.2 MB	代码最简洁，但性能较差
C++	156 ms	33.6 MB	性能最优，内存占用最小

代码亮点

🎯 使用归并排序和树状数组两种不同的解法，展示了不同的思路
💡 通过索引数组维护原始位置，避免了数据结构的重复构建
🔍 使用离散化技术优化树状数组的空间复杂度
🎨 代码结构清晰，变量命名规范，易于理解和维护

常见错误分析

🚫 忽略了数组元素可能相等的情况
🚫 归并排序过程中统计计数的位置错误
🚫 树状数组更新和查询操作的索引计算错误
🚫 没有正确处理数组边界情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
归并排序	O(nlogn)	O(n)	思路直观，实现相对简单	需要额外空间存储临时数组
树状数组	O(nlogn)	O(n)	更新和查询操作高效	需要离散化处理，实现较复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第315题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

方法一：归并排序

方法二：树状数组

图解思路

归并排序过程分析表

树状数组状态分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流