难度: 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 <= 5000 <= nums[i] <= 100运行时间: 29 ms
内存: 16.0 MB
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
a = dict()
b = sorted(nums)
for i , e in enumerate(b):
if e not in a.keys():
a[e]= i
for i, e in enumerate(nums):
b[i] = a[e]
return b
此题解采用了排序和哈希表的方法。首先，将输入数组nums排序并存储到数组b中。通过遍历排序后的数组b，构建一个哈希表a，其中每个元素e的值映射到其在数组b中首次出现的位置i。这个位置索引i实际上表示了小于元素e的元素数量，因为所有比e小的元素都位于其前面。然后，再次遍历原始数组nums，使用哈希表a将每个元素映射到它的计数结果，将这些结果存储在数组b中并返回。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
a = dict() # 创建哈希表存储元素和其对应的索引
b = sorted(nums) # 排序原数组
for i, e in enumerate(b): # 构建哈希表，只记录每个元素首次出现的位置
if e not in a.keys():
a[e] = i
for i, e in enumerate(nums): # 根据原数组元素查找并记录比当前元素小的元素数量
b[i] = a[e]
return b # 返回结果数组，重用数组b以节省空间
是的，这种方法已经考虑了数组中重复元素的情况。通过遍历排序后的数组并只在哈希表中记录每个元素首次出现的位置，可以确保即使元素在数组中重复出现，每个元素的计数仅代表小于该元素的不同元素的个数。这是因为在排序数组中，相同的元素是连续的，而只记录第一个元素的索引意味着忽略了后续相同元素的影响，从而精确计算出小于当前元素的数量。
在构建哈希表时选择只记录每个元素首次出现的位置是为了准确地计算小于当前元素的其他元素的数量。如果记录了每个元素每次出现的位置，那么在使用哈希表来查找小于特定元素的元素数量时，将无法区分哪些是重复的计数。通过只记录首次出现的位置，可以确保每个不同的元素对应一个唯一的索引，这个索引直接表示了在该元素之前的所有不同元素的数量。这种方法不仅提高了效率，还简化了逻辑处理，使得算法更加直观易懂。