How Many Numbers Are Smaller Than the Current Number

Условие

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

Примеры

Input: nums = [8, 1, 2, 2, 3]

Output: [4, 0, 1, 1, 3]

Explanation: В этом примере: Для 8: 4 числа меньше 8. Для 1: 0 чисел меньше 1. Для 2: 1 число меньше 2. Для 3: 3 числа меньше 3.

Input: nums = [6, 5, 4, 8]

Output: [2, 1, 0, 3]

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

Output: [0, 0, 0, 0]

Решение

fun smallerNumbersThanCurrent(nums: IntArray): IntArray {
    // Создаем массив для хранения результата, который будет содержать количество элементов,
    // меньших текущего элемента для каждого индекса
    val result = IntArray(nums.size)
    
    // Проходим по каждому элементу массива nums
    for (i in nums.indices) {
        var count = 0 // Переменная для подсчета элементов, меньших текущего элемента
        
        // Сравниваем текущий элемент nums[i] с остальными элементами массива
        for (j in nums.indices) {
            // Если элемент nums[j] меньше чем nums[i] и индексы не совпадают
            if (i != j && nums[j] < nums[i]) {
                count++ // Увеличиваем счётчик
            }
        }
        
        // Записываем количество элементов, меньших текущего, в результат на соответствующую позицию
        result[i] = count
    }
    
    // Возвращаем массив с результатами
    return result
}

Временная сложность

O(n^2) из-за двойного цикла для сравнения элементов.

Пространственная сложность

O(n) для хранения результатов в дополнительном массиве.