题目描述

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

例如：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）；以此类推。

解题思路

暴力法

最直接的想法是对于每个元素，遍历整个数组统计比它小的元素个数，时间复杂度 O(n²)。当数据量较大时效率很低。

排序 + 哈希表（O(n log n)）

本题的关键观察是：当我们把数组排序后，每个元素在排序数组中的下标，恰好就等于比它小的元素个数（因为排序后前面全是小于等于它的元素）。

具体步骤：

  1. 克隆并排序：将原数组 nums 克隆到 nums2，然后对 nums2 进行排序。
  2. 建立映射：遍历排序后的数组，建立”元素值 → 最小下标”的映射。注意处理重复元素——对于重复元素，应取第一次出现的位置（即最小的下标），因为比它小的元素个数应该是排序后第一个该值出现的下标。
    • 使用 map.put(nums2[i], Math.min(num, i)) 确保重复元素取最小下标。
  3. 生成结果：遍历原数组，对每个元素 nums[i]，直接从 map 中取出比它小的元素个数即可。

示例说明

以 nums = [8,1,2,2,3] 为例：

  • 排序后 nums2 = [1,2,2,3,8]
  • 建立映射：1→0, 2→1, 3→3, 8→4
  • 遍历原数组：8→4, 1→0, 2→1, 2→1, 3→3，结果 [4,0,1,1,3]。

复杂度分析

  • 时间复杂度：O(n log n)，排序 O(n log n)，两次遍历各 O(n)。
  • 空间复杂度：O(n)，需要克隆数组和哈希表的额外空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package code.J1365;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class J1365 {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] nums2 = nums.clone();
        Arrays.sort(nums2);
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums2.length; i++) {
            if (map.containsKey(nums2[i])) {
                int num = map.get(nums2[i]);
                map.put(nums2[i], Math.min(num, i));
            } else {
                map.put(nums2[i], i);
            }
        }
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = map.get(nums[i]);
        }
        return res;
    }
}