Сложность: 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⃣Верните результат.
😎 Решение:
package main
import (
"fmt"
"sort"
)
func countSmaller(nums []int) []int {
offset := 10000
size := 2 * 10000 + 1
tree := make([]int, size * 2)
result := make([]int, len(nums))
for i := len(nums) - 1; i >= 0; i-- {
smallerCount := query(0, nums[i] + offset, tree, size)
result[i] = smallerCount
update(nums[i] + offset, 1, tree, size)
}
return result
}
func update(index, value int, tree []int, size int) {
index += size
tree[index] += value
for index > 1 {
index /= 2
tree[index] = tree[index * 2] + tree[index * 2 + 1]
}
}
func query(left, right int, tree []int, size int) int {
result := 0
left += size
right += size
for left < right {
if left % 2 == 1 {
result += tree[left]
left++
}
left /= 2
if right % 2 == 1 {
right--
result += tree[right]
}
right /= 2
}
return result
}
func main() {
nums := []int{5, 2, 6, 1}
fmt.Println(countSmaller(nums))
}
Ставь 👍 и забирай 📚 Базу знаний