Easy

题目描述

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i]。

以数组形式返回答案。

示例 1：

输入：nums = [8,1,2,2,3]
输出：[4,0,1,1,3]
解释：
对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 
对于 nums[1]=1 不存在比它小的数字。
对于 nums[2]=2 存在一个比它小的数字：（1）。 
对于 nums[3]=2 存在一个比它小的数字：（1）。 
对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。

示例 2：

输入：nums = [6,5,4,8]
输出：[2,1,0,3]

示例 3：

输入：nums = [7,7,7,7]
输出：[0,0,0,0]

提示：

  • 2 <= nums.length <= 500
  • 0 <= nums[i] <= 100

解题思路

这道题要求统计数组中每个元素比它小的数字个数。根据数据规模和约束条件，我们可以考虑多种解法：

方法一：暴力解法

最直观的方法是对每个元素，遍历整个数组统计比它小的数字个数。时间复杂度为 O(n²)，但实现简单。

方法二：计数排序（推荐）

由于题目限制 0 ≤ nums[i] ≤ 100，数值范围很小，我们可以使用计数排序的思想。先统计每个数字出现的次数，然后计算前缀和，这样就能快速知道有多少个数字小于当前数字。

具体步骤：

  1. 创建计数数组统计每个数字的出现次数
  2. 计算前缀和，得到小于等于每个数字的元素个数
  3. 对于每个元素，直接从前缀和数组中查询结果

方法三：排序 + 二分查找

将数组排序后，对于每个原始位置的元素，在排序数组中二分查找第一个大于等于它的位置，该位置即为比它小的元素个数。

考虑到数据规模较小且数值范围有限，计数排序方法最优，时间复杂度 O(n + k)，其中 k=101。

代码实现

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> count(101, 0);
        
        // 统计每个数字出现的次数
        for (int num : nums) {
            count[num]++;
        }
        
        // 计算前缀和，得到小于等于每个数字的元素个数
        for (int i = 1; i < 101; i++) {
            count[i] += count[i - 1];
        }
        
        vector<int> result;
        for (int num : nums) {
            if (num == 0) {
                result.push_back(0);
            } else {
                result.push_back(count[num - 1]);
            }
        }
        
        return result;
    }
};

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        count = [0] * 101
        
        # 统计每个数字出现的次数
        for num in nums:
            count[num] += 1
        
        # 计算前缀和，得到小于等于每个数字的元素个数
        for i in range(1, 101):
            count[i] += count[i - 1]
        
        result = []
        for num in nums:
            if num == 0:
                result.append(0)
            else:
                result.append(count[num - 1])
        
        return result

public class Solution {
    public int[] SmallerNumbersThanCurrent(int[] nums) {
        int[] count = new int[101];
        
        // 统计每个数字出现的次数
        foreach (int num in nums) {
            count[num]++;
        }
        
        // 计算前缀和，得到小于等于每个数字的元素个数
        for (int i = 1; i < 101; i++) {
            count[i] += count[i - 1];
        }
        
        int[] result = new int[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            if (nums[i] == 0) {
                result[i] = 0;
            } else {
                result[i] = count[nums[i] - 1];
            }
        }
        
        return result;
    }
}

var smallerNumbersThanCurrent = function(nums) {
    return nums.map(num => nums.filter(n => n < num).length);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
暴力解法O(n²)O(1)
计数排序（推荐）O(n + k)O(k)
排序 + 二分O(n log n)O(n)

其中 n 为数组长度，k = 101 为数值范围大小。计数排序方法在此题中最优。

相关题目