Я пытался решить задачу в HackerRank , и решение требует:
К моему удивлению, я понимаю, что не существует структуры данных, поддерживающей обе операции.
Изначально я считаю, что SortedList соответствует всем требованиям, но НЕТ!
SortedDictionary имеет более быстрые операции вставки и удаления для несортированных данных, O (log n) , в отличие от O (n) для SortedList.
Чтение этой строки предполагает, что SortedDictionary может иметь то, что мне нужно, но ответ НЕТ! снова
Другое отличие между классами SortedDictionary и SortedList состоит в том, что SortedList поддерживает эффективный индексированный поиск ключей и значений через коллекции, возвращаемые свойствами Keys и Values. Нет необходимости повторно создавать списки при обращении к свойствам, поскольку списки являются просто оболочками для внутренних массивов ключей и значений. В следующем коде показано использование свойства Values для индексированного извлечения значений из отсортированного списка строк.
Они предлагают полностью извлечь коллекцию ключей, используя расширение ToList () и BinarySearch () поверх списка, но этот вызов ToList () уже приводит к тому, что производительность становится равной O (n) и нет смысла вызывать BinarySearch () .
С другой стороны, существует очень популярная реализация извлечения индекса O (log [n]) , которая заключается в добавлении поля Count к каждому узлу дерева, которое отслеживает, сколько элементы находятся в поддереве с корнем на этом узле. Это поле может быть обновлено во время поворота Red Black Tree в O (1) и потреблять только sizeof (int) дополнительной памяти на узел.
Вопросы:
Почему это не было реализовано с самого начала?
Какие плюсы есть в структуре данных SortedSet ?