Блог

Главная - Вопросы по программированию - Временная сложность метода фильтрации в наборе деревьев

Временная сложность метода фильтрации в наборе деревьев

#java #algorithm #kotlin #data-structures

#java #алгоритм #котлин #структуры данных

Вопрос:

 val x = TreeSet<Int>(compareBy { it.toString() })
x.add(2);
x.add(4)
x.add(5)
x.add(15)
x.add(1)
x.add(34)
println(x)
print(x.filter { it in 5..19 })

У меня есть некоторый вариант использования, аналогичный тому, который указан в качестве примера кода выше. У меня есть куча данных (размер может быть довольно большим) рассмотрим временные ряды, мне нужно отфильтровать те элементы из списка, которые находятся между 2 датами? Есть ли лучшее решение, чем подход O (n)?

Комментарии:

1. @Eran Это код Kotlin. it является неявным параметром в лямбда-функции.

Ответ №1:

Проблема здесь в том, что ваш TreeSet сортируется не в том же порядке, что и диапазон, поэтому мы не можем просто найти границы диапазона TreeSet и взять все промежуточное.

Если TreeSet было отсортировано в естественном порядке ( val x = TreeSet<Int>() ), вы могли бы просто сделать:

 val subset = x.subSet(5, true, 19, true)

Эта операция почти бесплатна (O (1)), вы просто платите (O(log (N))) за повторение этого TreeSet (построение итератора потребует двух поисков для границ подмножества).

После этого вы можете отсортировать его по-разному:

 println(subset.toSortedSet(compareBy { it.toString() }))