LeetCode 1365. 有多少小于当前数字的数字

Categories:

题目描述
思路分析
1. 解法一：计数前缀和（推荐）
相似题目

题目描述

✅ 1365. 有多少小于当前数字的数字

思路分析

解法一：计数前缀和（推荐）

核心思路：

数值范围在 0~100，使用频次数组统计。

构建前缀和，得到每个数之前的计数。

直接查询对应前缀和作为答案。

复杂度分析：

时间复杂度：O(n + C)，其中 n 表示数组长度，C=101。

空间复杂度：O(C)。

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] freq = new int[101];
        for (int num : nums) {
            freq[num]++;
        }

        int[] pre = new int[101];
        for (int i = 1; i <= 100; i++) {
            pre[i] = pre[i - 1] + freq[i - 1];
        }

        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[i] = pre[nums[i]];
        }

        return res;
    }
}

func smallerNumbersThanCurrent(nums []int) []int {
	freq := make([]int, 101)
	for _, num := range nums {
		freq[num]++
	}

	pre := make([]int, 101)
	for i := 1; i <= 100; i++ {
		pre[i] = pre[i-1] + freq[i-1]
	}

	res := make([]int, len(nums))
	for i, num := range nums {
		res[i] = pre[num]
	}

	return res
}

相似题目

题目	难度	考察点
1365. 有多少小于当前数字的数字	简单	计数
561. 数组拆分	简单	计数
1051. 高度检查器	简单	计数
1331. 数组序号转换	简单	排序
268. 丢失的数字	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/83500816