题目
给你一个数组 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
解答
- 暴力解法
思路：直接复制一份数组，将复制得到的数组进行排序，然后进行遍历比较，将得到的值添加到答案数组中，最后返回答案数组。
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> nums_sorted = nums; // 复制nums数组
sort(nums_sorted.begin(), nums_sorted.end()); // 将复制后的数组进行排序
vector<int> results; // 初始化答案数组
int len = nums.size(); // 得到数组的总长度
for (int i = 0; i < len; i++) { // 进行遍历
int result = 0; // 初始化大于nums[i]的元素的数量为0
for (int j = 0; j < len; j++) { // 在排序后的数组中进行遍历，以便得到精确的答案
if (nums_sorted[j] < nums[i]) {
result++; // 如果发现数组中有比nums[i]更小的数字，就把result进行++的操作
}
else{
break; // 否则就跳出循环（因为这是已经排序好的数组，这个元素不小于nums[i]那么之后的元素也都大于等于nums[i] 无需继续遍历
}
}
results.push_back(result); // 将答案push进答案数组中
}
return results; // 返回答案结果
}
};- 使用计数数组优化
思路：因为nums数组中元素的大小范围为0到100，所以可以设置一个统计各个数字分别有多少个的计数数组，然后利用计数数组计算整个数组中小于nums[i]的元素的个数。
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> count(101, 0); // 初始化计数数组，范围为0到100
vector<int> results; // 初始化结果数组
int len = nums.size(); // 获取数组长度
// 统计每个数字的出现次数
for (int i = 0; i < len; i++) {
count[nums[i]]++; // 统计当前数字出现的次数
}
// 遍历每个数字，计算小于当前数字的元素个数
for (int i = 0; i < len; i++) {
int temp_num = nums[i]; // 当前数字
int result = 0; // 小于当前数字的元素个数
for (int j = 0; j < temp_num; j++) { // 遍历计数数组
result += count[j]; // 累加小于当前数字的元素个数
}
results.push_back(result); // 将结果添加到结果数组中
}
return results; // 返回结果数组
}
};- 使用计数排序和前缀和
- 使用计数排序：题目中给出了限制条件，数组元素的范围是0到100，因此可以使用计数排序来替代排序函数，以提高效率。创建一个大小为101的计数数组，统计每个数字的出现次数，然后计算小于每个数字的元素个数。
- 使用前缀和：通过累加计算计数数组，可以得到每个数字的前缀和数组。前缀和数组的每个元素表示小于等于该数字的元素个数。然后，通过访问前缀和数组即可获取小于每个元素的元素个数。
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> count(101, 0); // 初始化计数数组
int len = nums.size();
// 统计每个数字的出现次数
for (int i = 0; i < len; i++) {
count[nums[i]]++;
}
// 计算前缀和数组
for (int i = 1; i <= 100; i++) {
count[i] += count[i - 1];
}
vector<int> results;
for (int i = 0; i < len; i++) {
if (nums[i] == 0) {
results.push_back(0); // 对于数字0，直接加入结果数组中
} else {
results.push_back(count[nums[i] - 1]); // 获取小于当前数字的元素个数
}
}
return results;
}
};