Сайт: https://easyoffer.ru/
Все каналы: t.me/+xGeAw6ckJ4liYzQy
Контакт для рекламы: @sendme_ads
Post #1393
89
Задача: 315. Count of Smaller Numbers After Self
Сложность: hard
Дан целочисленный массив nums, верните целочисленный массив counts, где counts[i] - это количество элементов справа от nums[i], которые меньше nums[i].
Пример:
👨💻 Алгоритм:
1⃣Реализуйте дерево отрезков (segment tree). Поскольку дерево инициализируется нулями, нужно реализовать только операции обновления и запроса. Установите смещение offset = 10^4.
2⃣Итерация по каждому числу в nums в обратном порядке. Для каждого числа выполните следующие действия:
Смещайте число на num + offset.
Запросите количество элементов в дереве отрезков, которые меньше текущего числа.
Обновите счетчик текущего числа в дереве отрезков.
3⃣Верните результат.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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 {
func countSmaller(_ nums: [Int]) -> [Int] {
let offset = 10000
let size = 2 * 10000 + 1
var tree = [Int](repeating: 0, count: size * 2)
var result = [Int]()
for num in nums.reversed() {
let smallerCount = query(0, num + offset, tree, size)
result.append(smallerCount)
update(num + offset, 1, tree, size)
}
return result.reversed()
}
private func update(_ index: Int, _ value: Int, _ tree: inout [Int], _ size: Int) {
var idx = index + size
tree[idx] += value
while idx > 1 {
idx /= 2
tree[idx] = tree[idx * 2] + tree[idx * 2 + 1]
}
}
private func query(_ left: Int, _ right: Int, _ tree: [Int], _ size: Int) -> Int {
var result = 0
var l = left + size
var r = right + size
while l < r {
if l % 2 == 1 {
result += tree[l]
l += 1
}
l /= 2
if r % 2 == 1 {
r -= 1
result += tree[r]
}
r /= 2
}
return result
}
}Ставь 👍 и забирай 📚 Базу знаний
