Ваш подход против предложенного с сортировкой кажется классическим компромиссом: какие операции дешевы, а какие дорогостоящи.
Я нахожу вашу запись немного запутанной, поэтому, пожалуйста, позвольте мне использовать мою собственную:
Пусть S будет набором. Пусть n будет количеством предметов в наборе: n = |S|. Пусть max будет самым большим числом в наборе: max = max(S). Пусть k будет количеством элементов, не входящих в набор: k = |{0,...,max} \ S|.
Для решения по сортировке мы могли бы очень дешево вставить все элементы n в S, используя хеширование. Это займет ожидаемый O(n). Затем для поиска пропущенных элементов k мы сортируем набор в O(nlogn), а затем определяем пропущенные элементы в O(n).
То есть общая стоимость добавления n элементов, а затем поиска недостающих k элементов занимает ожидаемое O(n) + O(nlogn) + O(n) = O(nlogn).
Вы предлагаете другой подход, в котором мы представляем набор в виде списка плотных подмножеств S. Как бы вы реализовали такую структуру данных? Я предлагаю отсортированное дерево (вместо списка), чтобы вставка стала эффективной. Потому что вы должны сделать для вставки нового элемента e? Я думаю, что вы должны:
- Найдите подмножество потенциальных кандидатов в дереве, куда можно добавить
e
- Если подмножество уже содержит
e, ничего не нужно делать.
- Если подмножество содержит
e+1, а другое подмножество содержит e-1, объедините подмножества вместе и добавьте e к результату
- Если подмножество уже содержит
e+1, но e-1 не содержится в S, добавьте e к этому подмножеству
- Если подмножество уже содержит
e-1, но e+1 не содержится в S, добавьте e к этому подмножеству
- В противном случае создайте новое подмножество, содержащее только элемент
e, и вставьте его в дерево.
Можно ожидать, что для поиска подмножеств, необходимых для вышеуказанных операций, потребуется O(logn). Операции 4. или 5. занимают постоянное время, если мы представляем подмножества в виде пар целых чисел (нам просто нужно уменьшить нижнюю границу или увеличить верхнюю границу). 3. и 6. потенциально требуют изменения древовидной структуры, но мы ожидаем, что это займет максимум O(logn), поэтому вся «вставка» не займет более O(logn).
Теперь, имея такую структуру данных, мы можем легко определить пропущенные числа k, пройдя по дереву по порядку и собрав числа, которых нет ни в одном из подмножеств. Затраты линейны по количеству узлов в дереве, которое составляет <= n/2, поэтому общие затраты для этого составляют O(n).
Однако, если мы снова рассмотрим всю последовательность операций, мы получим n вставок O(nlogn) + O(n) для поиска k пропущенных чисел, поэтому общие затраты снова будут O(nlogn).
Это не лучше, чем ожидаемые затраты на первый алгоритм.
Третье решение - использовать логическое array для представления набора и одно целое число max для самого большого элемента в наборе.
Если элемент e добавлен в набор, вы устанавливаете array[e] = true. Вы можете реализовать переменный размер набора, используя расширение таблицы , поэтому затраты на вставку элемента в массив постоянны.
Чтобы извлечь недостающие элементы, вы просто собираете эти элементы f, где array[f] == false. Это займет O(max).
Таким образом, общие затраты на вставку n элементов и нахождение k отсутствующих элементов: O(n) + O(max). Тем не менее, max = n + k, и поэтому мы получаем как общие расходы O(n + k).
Четвертый метод, который представляет собой переход между третьим методом и методом, использующим хеширование, является следующим, который также использует хеширование, но не требует сортировки.
Сохраните ваш набор S в хэш-наборе, а также сохраните максимальный элемент в S в переменной max. Чтобы найти пропущенные k, сначала сгенерируйте результирующий набор R, содержащий все числа {0,...,max}. Затем выполните итерацию по S и удалите каждый элемент в S из R.
Расходы на это также O(n + k).