Count of Smaller Numbers After Self,LeetCode,315

LeetCode 上的第 315 题 “Count of Smaller Numbers After Self” 是一个中等难度的题目。题目要求对于数组中的每一个元素，计算其右边所有比它小的元素的数量。

题目描述

给定一个整数数组 nums，返回一个新的数组 counts，其中 counts[i] 表示 nums[i] 右边所有比 nums[i] 小的元素的数量。

示例

输入: [5, 2, 6, 1]

输出: [2, 1, 1, 0]

解释:

• 5 的右边有 2 和 1，比 5 小，所以 counts[0] = 2
• 2 的右边有 1，比 2 小，所以 counts[1] = 1
• 6 的右边有 1，比 6 小，所以 counts[2] = 1
• 1 的右边没有比 1 小的元素，所以 counts[3] = 0

解法思路

有多种方法可以解决这个问题，以下是几种常见的思路：

1. 暴力解法

最直接的方法是使用双重循环，对于每个元素，遍历其右边的所有元素并计数。这种方法的时间复杂度是 O(n^2)，在数据量较大时效率较低。

2. 归并排序

使用归并排序的思想，可以在排序的同时统计逆序对的数量。具体步骤如下：

1. 分解：将数组分成两半，递归处理每一半。
2. 合并：在合并过程中，统计左边元素比右边元素大的情况，这样可以知道左边元素右边有多少比它小的元素。

这种方法的时间复杂度是 O(n log n)。

3. 树状数组（Binary Indexed Tree，BIT）

树状数组是一种高效的数据结构，可以用来处理区间和的问题。具体步骤如下：

1. 离散化：由于树状数组需要处理下标，先将数组进行离散化处理。
2. 逆序遍历：从右到左遍历数组，使用树状数组统计当前元素之前比它小的元素的数量。

这种方法的时间复杂度也是 O(n log n)。

代码实现

以下是使用归并排序思想的 Python 代码实现：

class Solution: def countSmaller(self, nums): def merge_sort(enum): half = len(enum) // 2 if half: left, right = merge_sort(enum[:half]), merge_sort(enum[half:]) for i in range(len(enum))[::-1]: if not right or left and left[-1][1] > right[-1][1]: smaller[left[-1][0]] += len(right) enum[i] = left.pop() else: enum[i] = right.pop() return enum

    smaller = [0] * len(nums)
    merge_sort(list(enumerate(nums)))
    return smaller

解释

1. enumerate(nums)：将 nums 数组的每个元素与其下标绑定，形成 (index, value) 的元组。
2. merge_sort：自定义的归并排序函数，不仅排序，还在合并过程中统计逆序对。
3. smaller：用于存储每个元素右边比它小的元素的数量。

总结

“Count of Smaller Numbers After Self” 是一个考察数据结构和算法的题目，通过归并排序或树状数组可以实现高效的解决方案。理解这些方法不仅有助于解决本题，还能提升对排序和区间查询问题的处理能力。