Блог

Если у меня есть массив в виде [7, 11, 13, 9, 4, 6], и пользовательский ввод равен 10,
я хочу, чтобы целое число было чуть выше (или равно) 10 (в данном случае 11) и заменило его целым числом — 10 (11 — 10)
, которое я не могу заказатьсписок и двоичный поиск, поскольку я должен вернуть индекс обновленного элемента.
Я изучил порядок пар (индекс, целое число), а затем двоичный поиск, но затем после обновления мне нужно повторно отсортировать массив пар для следующего пользовательского ввода.

исходный массив = [7, 11, 13, 9, 4, 6]
отсортированный массив = [4, 6, 7, 9, 11, 13]
пользовательский ввод = 10
вывод = 1 (индекс обновленного целого числа)

обновленный отсортированный массив = [4, 6, 7, 9, 1, 13]
повторно отсортированный массив = [1, 4, 6, 7, 9, 13]
пользовательский ввод = 4
…

Какая структура данных была бы подходящей для реализации этого?

Вы можете использовать упорядоченный набор для хранения кортежей (значений, индексов). Вы можете определить пользовательские функции сравнения в соответствии с вашей целью (это зависит от рассматриваемого языка программирования).

Операции упорядоченного набора включают:

1. Добавьте элемент.
2. Удалите элемент.
3. Поиск элемента.
4. Поиск элемента, большего или равного заданному элементу.
5. Поиск элемента, превышающего заданный элемент.

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

Некоторые языки программирования (например, set в c ) имеют предопределенные структуры данных, поэтому вам не нужно реализовывать их с нуля (только для использования). Внутренняя реализация упорядоченного набора обычно представляет собой красно-черное дерево (c ) или дерево AVL.

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