欢迎大家参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
题目链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits/
给你一个数组 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 <= 500
- 0 <= nums[i] <= 100
两层for循环暴力查找，时间复杂度明显为O(n^2)。
那么我们来看一下如何优化。
首先要找小于当前数字的数字，那么从小到大排序之后，该数字之前的数字就都是比它小的了。
所以可以定义一个新数组，将数组排个序。
排序之后，其实每一个数值的下标就代表这前面有几个比它小的了。
代码如下：
vector<int> vec = nums;
sort(vec.begin(), vec.end()); // 从小到大排序之后，元素下标就是小于当前数字的数字
此时用一个哈希表hash（本题可以就用一个数组）来做数值和下标的映射。这样就可以通过数值快速知道下标（也就是前面有几个比它小的）。
此时有一个情况，就是数值相同怎么办？
例如，数组：1 2 3 4 4 4 ，第一个数值4的下标是3，第二个数值4的下标是4了。
这里就需要一个技巧了，在构造数组hash的时候，从后向前遍历，这样hash里存放的就是相同元素最左面的数值和下标了。 代码如下：
int hash[101];
for (int i = vec.size() - 1; i >= 0; i--) { // 从后向前，记录 vec[i] 对应的下标
hash[vec[i]] = i;
}最后在遍历原数组nums，用hash快速找到每一个数值 对应的 小于这个数值的个数。存放在将结果存放在另一个数组中。
代码如下：
// 此时hash里保存的每一个元素数值 对应的 小于这个数值的个数
for (int i = 0; i < nums.size(); i++) {
vec[i] = hash[nums[i]];
}流程如图：
关键地方讲完了，整体C++代码如下：
class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
vector<int> vec = nums;
sort(vec.begin(), vec.end()); // 从小到大排序之后，元素下标就是小于当前数字的数字
int hash[101];
for (int i = vec.size() - 1; i >= 0; i--) { // 从后向前，记录 vec[i] 对应的下标
hash[vec[i]] = i;
}
// 此时hash里保存的每一个元素数值 对应的 小于这个数值的个数
for (int i = 0; i < nums.size(); i++) {
vec[i] = hash[nums[i]];
}
return vec;
}
};可以排序之后加哈希，时间复杂度为O(nlogn)
/**
* 解法一：暴力
* 时间复杂度：O(n^2)
* 空间复杂度：O(n)
*/
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] res = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (nums[j] < nums[i] && j != i) { // 注意 j 不能和 i 重合
res[i]++;
}
}
}
return res;
}
}/**
* 优化：排序 + 哈希表
* 时间复杂度：O(nlogn)
* 空间复杂度：O(n)
*/
class Solution {
public int[] smallerNumbersThanCurrent(int[] nums) {
int[] res = Arrays.copyOf(nums, nums.length);
Arrays.sort(res); // 是对 res 排序，nums 中顺序还要保持
int[] hash = new int[101]; // 使用哈希表，记录比当前元素小的元素个数
for (int i = res.length - 1; i >= 0; i--) { // 注意：从后向前
hash[res[i]] = i; // 排序后，当前下标即表示比当前元素小的元素个数
}
// 此时 hash中保存的每一个元素数值 便是 小于这个数值的个数
for (int i = 0; i < res.length; i++) {
res[i] = hash[nums[i]];
}
return res;
}
}