У меня есть задание написать алгоритм для поиска дубликата в динамическом сортированном массиве. Я хочу написать этот algoirthm, но перед запуском я должен знать структуру данных Dynamic Sorted Array, но я этого не знаю. Я пытался использовать Google, но я не мог найти ничего подобного Dynamic Sorted Array. не могли бы вы направить меня? Какова структура данных и как они выглядят? Благодарю.Помогите узнать структуру данных
Давайте посмотрим, что вам нужно понять, что массив Dynamic рассортированные:
Вы уже знаете, что упорядоченный массив, поэтому давайте попробуем понять, что dynamic array является: Это не растут, способный массив, в котором нет ограничение размера массива.
Таким образом, чтобы подвести итог, то нужно записать массив, который является:
А. Рассортировано
B. Динамический характер (расширение)
Как реализовать? Прочитано Dynamic arrays overview and implementation in Java and C++
Я предполагаю, что это означает массив, длина которого является динамической (т. Е. Неизвестной во время компиляции) и значения которой сортируются.
Я думаю, что ваш инструктор просто ссылается на массив, который может меняться и сортироваться, поэтому вы можете предположить, что он всегда в правильном порядке и что он имеет переменную длину. Если алгоритм должен быть написан в псевдокоде, это, вероятно, все, что вам нужно знать.
Я никогда не слышал об этой структуре данных, но на основе отдельных слов, я бы предположил, что это:
get(index) и set(index) O (1) доступа.Я не думаю, что такая структура данных очень эффективна для поиска дубликатов. Я бы предпочел какую-то карту, если вам не нужны очень простые алгоритмы.
Почему это не очень эффективно? Карта не позволяет дублировать, так что да, это было бы наиболее эффективным при простом возвращении 0. Если вы имеете в виду использование этого в качестве посредника для определения/поиска дубликатов, то да, карта была бы хорошо подходит. – nlucaroni
Я интерпретировал исходный вопрос как * реализую функцию 'findAllDuplicates' *. Для простой реализации на основе массива, для которой потребуется время O (N). Поэтому я предпочел подход, основанный на карте, когда такой поиск потребует только постоянного времени.Основная идея заключалась бы в том, чтобы иметь два внутренних набора 'count
Я бы сказал, что у вас может быть опечатка в вашем задании. Возможно, он должен прочитать «отсортированный динамический массив».
Однако динамический массив, который всегда вставляет новые элементы в отсортированном порядке, вероятно, соответствует этой терминологии. Так что берите динамический массив:
[2] [5] [7] [9]
Вставка элемента '8' приведет к следующему массива:
[2] [5] [ 7] [8] [9]
Разве это не просто список элементов, которые сами себя сортируют? – cdhowie