leetcode
leetcode 1251 ~ 1300
有多少小于当前数字的数字

有多少小于当前数字的数字

难度:

标签:

题目描述

代码结果

运行时间: 29 ms, 内存: 16.0 MB


/*
题目思路:
1. 使用 Java Stream API 实现同样的逻辑。
2. 对于每个元素,计算比其小的元素个数,可以通过过滤数组中的元素并计数。
3. 使用 IntStream.range 和 map 方法来遍历数组并生成结果。
4. 将结果转换为数组并返回。
*/

import java.util.stream.IntStream;

public int[] smallerNumbersThanCurrent(int[] nums) {
    return IntStream.range(0, nums.length)
                    .map(i -> (int) IntStream.range(0, nums.length)
                                             .filter(j -> nums[j] < nums[i])
                                             .count())
                    .toArray();
}

解释

方法:

此题解采用了排序和哈希表的方法。首先,将输入数组nums排序并存储到数组b中。通过遍历排序后的数组b,构建一个哈希表a,其中每个元素e的值映射到其在数组b中首次出现的位置i。这个位置索引i实际上表示了小于元素e的元素数量,因为所有比e小的元素都位于其前面。然后,再次遍历原始数组nums,使用哈希表a将每个元素映射到它的计数结果,将这些结果存储在数组b中并返回。

时间复杂度:

O(n log n)

空间复杂度:

O(n)

代码细节讲解

🦆
在解题中使用哈希表来存储元素首次出现的索引,这种方法是否考虑了数组中重复元素的情况?如何处理?
是的,这种方法已经考虑了数组中重复元素的情况。通过遍历排序后的数组并只在哈希表中记录每个元素首次出现的位置,可以确保即使元素在数组中重复出现,每个元素的计数仅代表小于该元素的不同元素的个数。这是因为在排序数组中,相同的元素是连续的,而只记录第一个元素的索引意味着忽略了后续相同元素的影响,从而精确计算出小于当前元素的数量。
🦆
为什么在构建哈希表时选择只记录每个元素首次出现的位置,而不是每次出现的位置?
在构建哈希表时选择只记录每个元素首次出现的位置是为了准确地计算小于当前元素的其他元素的数量。如果记录了每个元素每次出现的位置,那么在使用哈希表来查找小于特定元素的元素数量时,将无法区分哪些是重复的计数。通过只记录首次出现的位置,可以确保每个不同的元素对应一个唯一的索引,这个索引直接表示了在该元素之前的所有不同元素的数量。这种方法不仅提高了效率,还简化了逻辑处理,使得算法更加直观易懂。

相关问题