1365. How Many Numbers Are Smaller Than the Current Number

Задача

Дан массив nums. Для каждого элемента верните, сколько чисел в массиве меньше него.

Примеры

Пример 1

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]

Пояснение

Для 8 меньше него 4 числа (1,2,2,3); для 1 — ни одного; для каждой 2 — одно (1); для 3 — три (1,2,2).

Пример 2

Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Пример 3

Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Решение

Решение

/**
 * Сложность по времени: O(n + k), где n — количество элементов, k — диапазон чисел (101).
 * - Мы проходим по массиву nums один раз, чтобы заполнить частоты: O(n).
 * - Проходим по частотному массиву (размером 101), чтобы посчитать префиксы: O(k).
 * - Снова проходим по nums, чтобы собрать ответ: O(n).
 * - Итого: O(n), так как k — константа (100).
 *
 * Сложность по памяти: O(k)
 * - Используется массив count размером 101 элемент (константа O(1) в контексте задачи).
 */
var smallerNumbersThanCurrent = function(nums) {
    const len = Math.max(...nums);
    const count = new Array(len + 1).fill(0);
 
    // 1. Считаем частоту каждого числа
    for (const num of nums) {
        count[num]++;
    }
 
    // 2. Превращаем частоты в префиксные суммы.
    // count[i] будет хранить количество чисел, которые МЕНЬШЕ или РАВНЫ i.
    // Но для текущей задачи нам нужно строго меньше, поэтому будем
    // аккуратно брать значение предыдущего индекса при формировании ответа.
    for (let i = 1; i <= len; i++) {
        count[i] += count[i - 1];
    }
 
    // 3. Формируем ответ
    // Берем значение из (num - 1), так как оно содержит
    // сумму всех частот чисел, строго меньших num
    return nums.map((num) => arr[num - 1]);
};
 

Решение 2 (Сортировка + Хеш-таблица)

/**
 * Сложность по времени: O(n log n)
 * - Сортировка массива занимает O(n log n).
 * - Проход для заполнения Map занимает O(n).
 * - Финальный map занимает O(n).
 * - Итого доминирует сортировка: O(n log n).
 *
 * Сложность по памяти: O(n)
 * - Мы создаем копию массива sortedNums: O(n).
 * - Мы создаем Map для хранения индексов: O(n).
 */
var smallerNumbersThanCurrent = function(nums) {
    // Создаем отсортированную копию
    const sortedNums = [...nums].sort((a, b) => a - b);
    const map = new Map();
 
    // Заполняем карту: Число -> Первое вхождение индекса
    // Индекс в отсортированном массиве как раз равен количеству чисел перед ним
    for (let i = 0; i < sortedNums.length; i++) {
        const num = sortedNums[i];
        // Если число уже есть, не перезаписываем (нам нужен индекс ПЕРВОГО вхождения)
        if (!map.has(num)) {
            map.set(num, i);
        }
    }
 
    // Собираем ответ, используя исходный порядок nums
    return nums.map(num => map.get(num));
};