题目描述
- 时间：2020-03-05
- 题目链接：https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/
- tag：
triebinary search - 难度：简单
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
Example 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）。
Example 2:
输入：nums = [6,5,4,8]
输出：[2,1,0,3]
Example 3:
输入：nums = [7,7,7,7]
输出：[0,0,0,0]
Note:
2 <= nums.length <= 500
0 <= nums[i] <= 100
参考答案
按照过程
参考代码
暴力解法，按照题目字义的理解。但是实际上时间复杂度高 O(n^2)
/*
* @lc app=leetcode id=1365 lang=python
*
* [1365] 有多少小于当前数字的数字
*/
class Solution(object):
def smallerNumbersThanCurrent(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
result = [0]*len(nums)
for key,num in enumerate(nums):
for j,v in enumerate(nums):
if key!=j and v<num:
result[key] +=1
return result
频次数组 + 前缀和
注意到数字的值域范围为 [0,100] ，所以可以考虑建立一个频次数组 cnt[i]，表示数字 i 出现的次数，那么对于数字 i 而言，它的答案就是
\sum_{j=0}^{i-1}cnt[j]
即小于它的数字出现个数之和，直接算需要遍历 [0,i-1]的 cnt求和，仍需要线性的时间去计算，但我们注意到这个答案是一个前缀和，所以我们可以再对 cnt 数组求前缀和。那么对于数字 i 的答案就是 cnt[i-1]，算答案的时间复杂度从 O(n) 降到了 O(1) 。
最后整个算法流程为：遍历数组元素，更新 cnt 数组，即 cnt[nums[i]]+=1 ，然后对 cnt 数组求前缀和，最后遍历数组元素，对于相应的数字 O(1) 得到答案即可。
class Solution(object):
def smallerNumbersThanCurrent(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
cnt = [0]*101
result = [0]*len(nums)
for num in nums:
cnt[num] +=1
# cnt[i]记录的是比 i+1小的个数
for i in range(1,101):
cnt[i] +=cnt[i-1]
for j in range(len(nums)):
# 防止nums[j]-1 小于0 数组溢出
if nums[j]:
result[j] = cnt[nums[j]-1]
return result
复杂度分析
时间复杂度：统计 cnt 数组的前缀和需要 O(S) 的时间，遍历数组需要 O(n)的时间，所以总时间复杂度为 O(S+n) ，其中 S为值域大小，n=nums.length 。
空间复杂度：O(S)，需要开一个值域大小的数组。
排序
我们将 nums数组按数字大小从小到大排序，那么对于第 i 个数字 x ，数组中在它前面的数字一定小于等于它，而题目要求小于它的数字个数，所以我们可以对于位置 i 记录一个变量 pre_i ，表示位置 i 往前第一个不等于 x 的数字下标。对于数字 x ，答案就是 pre_i+1 ，因为数组下标是从 0 开始的，所以需要额外加一。pre_{i} 需要分两种情况更新，如果前面一个数字等于当前数字 x ，那么 pre_i=pre_{i-1}，否则 pre_i=i-1，这样即能 O(1) 推出 pre_i。同时注意到 pre_i只与前一个位置有关，所以可以不用数组存 pre_i，直接用一个变量 prepre 表示前一个位置的 pre_{i-1} ，然后不断更新 pre 即可。最后整个算法流程为：对每个数字用一个二元组 (number_i,index\ of\ number_i) 表示数字大小和数字在nums 数组中的下标，用 tmp 数组存储所有二元组，按数字 number_i从小到大排序 tmp数组，最后遍历 tmp 数组，按上文说的方法的维护 pre 变量，对于 tmp 数组里第 i个元素的答案，应放在答案数组中的第 index\ of\ number_i个位置里 。
class Solution:
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
n = len(nums)
vec = [0] * n
tmp = sorted([(nums[i], i) for i in range(n)])
pre = -1
for i in range(n):
if i != 0 and tmp[i][0] != tmp[i - 1][0]:
pre = i - 1
vec[tmp[i][1]] = pre + 1
return vec
此方法总的时间复杂度为 O(nlogn+n)=O(nlogn)。 不过理解起来就有点不易了
比较常规的一种解法, 大部分人采用的做法, 这里就不再赘述
其他优秀解答
暂无