PHP | LeetCode

Задача: 315. Count of Smaller Numbers After Self Сложность: hard Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i]. Пример:

Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

👨‍💻 Алгоритм: 1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4. 2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия: Смещайте число на num + offset. Запросите количество элементов в дереве отрезков, которые меньше текущего числа. Обновите счетчик текущего числа в дереве отрезков. 3⃣Верните результат. 😎 Решение:

class Solution {
    function countSmaller($nums) {
        $offset = 10000;
        $size = 2 * 10000 + 1;
        $tree = array_fill(0, $size * 2, 0);
        $result = [];

        for ($i = count($nums) - 1; $i >= 0; $i--) {
            $smallerCount = $this->query(0, $nums[$i] + $offset, $tree, $size);
            $result[] = $smallerCount;
            $this->update($nums[$i] + $offset, 1, $tree, $size);
        }
        return array_reverse($result);
    }

    function update($index, $value, &$tree, $size) {
        $index += $size;
        $tree[$index] += $value;
        while ($index > 1) {
            $index = intdiv($index, 2);
            $tree[$index] = $tree[$index * 2] + $tree[$index * 2 + 1];
        }
    }

    function query($left, $right, &$tree, $size) {
        $result = 0;
        $left += $size;
        $right += $size;
        while ($left < $right) {
            if ($left % 2 == 1) {
                $result += $tree[$left];
                $left++;
            }
            $left = intdiv($left, 2);
            if ($right % 2 == 1) {
                $right--;
                $result += $tree[$right];
            }
            $right = intdiv($right, 2);
        }
        return $result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний