Сложность: easy
Дан массив nums. Для каждого элемента nums[i] определите, сколько чисел в массиве меньше его. То есть, для каждого nums[i] вам нужно посчитать количество допустимых j, таких что j != i и nums[j] < nums[i].
Верните ответ в виде массива.
Пример:
Input: nums = [6,5,4,8]
Output: [2,1,0,3]
👨💻 Алгоритм:
1⃣Создание копии и сортировка массива:
Создайте отсортированную копию массива nums, чтобы легко находить количество элементов, меньших текущего.
2⃣Поиск индекса каждого элемента:
Для каждого элемента nums[i] найдите его индекс в отсортированной копии массива. Этот индекс указывает количество элементов, меньших nums[i].
3⃣Формирование ответа:
Сформируйте массив ответов, где каждый элемент будет соответствовать количеству чисел, меньших текущего.
😎 Решение:
#include <vector>
#include <algorithm>
class Solution {
public:
std::vector<int> smallerNumbersThanCurrent(std::vector<int>& nums) {
std::vector<int> sortedNums = nums;
std::sort(sortedNums.begin(), sortedNums.end());
std::vector<int> result;
for (int num : nums) {
result.push_back(std::find(sortedNums.begin(), sortedNums.end(), num) - sortedNums.begin());
}
return result;
}
};
Ставь 👍 и забирай 📚 Базу знаний