Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != iandnums[j] < nums[i].
Return the answer in an array.
Example 1:
Input:
nums = [8,1,2,2,3]
Output:
[4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).
Example 2:
Input:
nums = [6,5,4,8]
Output:
[2,1,0,3]
Example 3:
Input:
nums = [7,7,7,7]
Output:
[0,0,0,0]
Constraints:
2 <= nums.length <= 5000 <= nums[i] <= 100
使用桶排序，在nums的大小范围内可以达到常数乘N的复杂度。
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
int a[101] = {0};
vector<int> b;
for( auto num : nums ){
a[num]++;
}
for( int i = 1 ; i < 101 ; i ++ ){
a[i] = a[i] + a[i-1];
}
for( int i = 0 ; i < nums.size() ; i ++ ){
if( nums[i] == 0 ) b.push_back(0);
else b.push_back(a[nums[i]-1]);
}
return b;
}
};
优化1：使用桶排序而不使用暴力排序。
优化2：使用单个数组存储桶内容与前序内容。
0 条评论