Keshawn_lu's Blog

Leetcode 1365. 有多少小于当前数字的数字

字数统计: 452阅读时长: 2 min
2020/10/27 Share

题目简介:

给你一个数组 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 <= 500
  • 0 <= nums[i] <= 100

思路:

由于数字的大小范围已确定,所以定义一个数组来统计每个数字出现的次数

然后将此数组中的每个元素累加前面的元素,从而count[i]的含义便为 比数字i小的元素个数。

最后将结果依次加入答案数组即可。

tip:

  • 由于防止数字0出错,以count[nums[i] + 1]进行存储。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {

vector<int> count(102, 0);
vector<int> res;

for(int i = 0; i < nums.size(); i++){

count[nums[i] + 1]++; //记录每个数字出现次数,防止0出错
}

for(int i = 2; i < 102; i++){

count[i] += count[i - 1]; //累加前面数字的出现次数
}

for(int i = 0; i < nums.size(); i++){

res.push_back(count[nums[i]]);
}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: