题目地址
难度：⭐
题目描述：
给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
示例1：
1
2
3
4
5
6
7
8
| 输入：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：
1
2
| 输入：nums = [6,5,4,8]
输出：[2,1,0,3]
|
示例3：
1
2
| 输入：nums = [7,7,7,7]
输出：[0,0,0,0]
|
提示：
2 <= nums.length <= 5000 <= nums[i] <= 100
🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️解题过程🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️🙋♂️
解题过程：
思路：
遍历数组nums，对每一个元素和数组nums中的所有元素进行比较，大于则数目加1。
c++代码：(执行用时68ms，击败17.74%，内存消耗10.1M，击败77.40%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> result;
int num;
for(int i=0;i<nums.size();++i){
num=0;
for(int j=0;j<nums.size();++j){
if(nums[j]<nums[i]){
++num;
}
}
result.push_back(num);
}
return result;
}
};
|
方法一：暴力
比较容易想到的一个方法是，对于数组中的每一个元素，我们都遍历数组一次，统计小于当前元素的数的数目。
c++代码：（执行16ms，击败56.92%，内存10.7M，击败7.63%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> ret;
int n = nums.size();
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (nums[j] < nums[i]) {
cnt++;
}
}
ret.push_back(cnt);
}
return ret;
}
};
|
复杂度分析
- 时间复杂度：$O(N^2)$，其中 $N$ 为数组的长度。
- 空间复杂度：$O(1)$。注意我们不计算答案数组的空间占用。
方法二：快速排序
我们也可以将数组排序，并记录每一个数在原数组中的位置。对于排序后的数组中的每一个数，我们找出其左侧第一个小于它的数，这样就能够知道数组中小于该数的数量。
c++代码：（执行32ms，击败36.78%，内存10.7M，击败7.90%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<pair<int, int>> data;
int n = nums.size();
for (int i = 0; i < n; i++) {
data.emplace_back(nums[i], i);
}
sort(data.begin(), data.end());
vector<int> ret(n, 0);
int prev = -1;
for (int i = 0; i < n; i++) {
if (prev == -1 || data[i].first != data[i - 1].first) {
prev = i;
}
ret[data[i].second] = prev;
}
return ret;
}
};
|
复杂度分析
时间复杂度：$O(Nlog N)$，其中 $N$ 为数组的长度。排序需要 $O(Nlog N)$的时间，随后需要 $O(N)$ 时间来遍历。
空间复杂度：$O(N)$。因为要额外开辟一个数组。
方法三：计数排序
注意到数组元素的值域为 [0,100]，所以可以考虑建立一个频次数组 $cnt$ ，$cnt[i]$ 表示数字 $i$ 出现的次数。那么对于数字 $i$i而言，小于它的数目就为 $cnt[0…i-1]$ 的总和。
c++代码：（执行12ms，击败73.62%，内存10.3M，击败39.54%）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> cnt(101, 0);
int n = nums.size();
for (int i = 0; i < n; i++) {
cnt[nums[i]]++;
}
for (int i = 1; i <= 100; i++) {
cnt[i] += cnt[i - 1];
}
vector<int> ret;
for (int i = 0; i < n; i++) {
ret.push_back(nums[i] == 0 ? 0: cnt[nums[i]-1]);
}
return ret;
}
};
|
复杂度分析
时间复杂度：$O(N + K)$，其中 $K$为值域大小。需要遍历两次原数组，同时遍历一次频次数组 $cnt$ 找出前缀和。
空间复杂度：$O(K)$。因为要额外开辟一个值域大小的数组。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：
还是最直观的暴力方法最好想，官方题解有多种做法。提交后的执行用时波动也挺大的。
