Среди простых и очень естественных алгоритмов есть такие, которые можно описать парой слов, однако прежде чем один такой действительно выйдет из-под рук, можно вспомнить все смертоносные заклинания, которым только учили в Хогвартсе. Двоичный поиск, быстрое возведение в степень, алгоритм Евклида - всем известные вещи о пяти строках кода, которые, тем не менее, не принято писать правильно с первого раза.
Вот, а я расскажу о совсем скучном алгоритме, который отбирает уникальные элементы в последовательности. Точнее, для каждого отрезка равных элементов этой последовательности он оставляет только первый:
[1 1 1 1 1 1 2 2 3 4 4 4 4 4 2 3 5 6 7 7 7 7 8 1] -> [1 2 3 4 2 3 5 6 7 8 1]
Самый главный плюс его в том, что на эту спорную деятельность он не отнимет много вашего времени - один проход по массиву, или O(n).
Казалось бы, проверить соседние элементы и, если они равны, удалить правый и пойти дальше, закончив работу ровно за один проход. Однако, хоть проход и действительно будет один, компьютер по завершении работы будет смотреть вам в глаза виновато: ему потребуется гораздо больше времени, чем O(n), потому что исходная последовательность может располагаться в непрерывной области памяти, из которой нельзя удалять, и единственный выход - сдвигать элементы... И вообще, хватит оправдываться - удалять нельзя! Вот такие новые условия задачи: элементы удалять нельзя, только менять их значения.
А как насчёт того, чтобы рассматривать отрезки с одинаковыми значениями один за другим? Вот так:
[1 1 1 1 1 1 | 2 2 | 3 | 4 4 4 4 4 | 2 | 3 | 5 | 6 | 7 7 7 7 | 8 | 1]
Тогда всё, о чём нам надо будет заботиться, - это 1) находить начало очередного отрезка, 2) находить его конец и начало следующего, 3) после шага 2 каждый раз копировать не более одного элемента.
Вот, скажем, определились границы первого отрезка 1 1 1 1 1 1 | 2. По условию задачи ото всех элементов начиная со второй единицы нужно избавиться, поэтому сразу же копируем двойку на место второй единицы: 1 2 1 1 1 1 | 2. Но что делать с оставшимися единицами, которые всё путают?
А сделаем вот так: 1 | 2 2 2 2 2 2 ... - теперь всё выглядит намного лучше: есть канонический (из одного элемента) отрезок с единицей, есть отрезок из двоек, конец которого ещё предстоит найти, и больше ничего лишнего. Только откуда все эти двойки? Там же вверху было чё-то про одно копирование максимум... А двоек и нет: мы их видим, потому что [нас только что отключили от Матрицы] мы так хотим: ведь правда, что происходит с теми оставшимися единицами, нам всё равно настолько, что мы спокойно можем назвать их двойками и с облегчением идти дальше. Неприятный осадок, который остаётся в таком случае, - это что такой подход работает, пока мы не настигнем конца последовательности: за последним исправленным отрезком будет твориться хаос из дублей и мешанины, которой от нашего алгоритма пользователь совсем не ожидал. Хорошая новость: unique возвращает позицию нового конца последовательности, начиная с которой дальше будет твориться хаос, и это нормально.
Итак, алгоритм ещё раз:
1. заводим два маркера: на начало отрезка равных элементов - equal_begin - и на позицию за концом - equal_end (изначально это первые два элемента последовательности), и отдельно переменную длины позиции - equal_distance;
2. пока не коснёмся equal_end конца последовательности, повторяем шаг 3
2. пока не коснёмся equal_end конца последовательности, повторяем шаг 3
3. проверяем позицию за концом: если её элемент равен начальному, то это ещё не за концом - сдвигаем equal_end, инкрементируем equal_distance; если же не равен, смотрим, канонический ли это отрезок (равен ли equal_distance единице), и в зависимости от этого либо просто сдвигаем оба маркера, либо сдвигаем только equal_begin, копируем туда значение по equal_end и двигаем его. В обоих случаях длина текущего отрезка не меняется.
4. возвращаем позицию за equal_begin
Важное замечание: входная последовательность подаётся по правилам STL: {начальный элемент, элемент за концом}.
4. возвращаем позицию за equal_begin
Важное замечание: входная последовательность подаётся по правилам STL: {начальный элемент, элемент за концом}.
И код на C++ для лабораторок:
template<typename It>
It uniq(It begin, It end)
{
It range_end(begin);
++range_end;
size_t equal_distance(1);
while (range_end != end)
{
// current segment still going
if (*range_end == *begin)
{
++range_end;
++equal_distance;
}
// the next segment begins
else
{
if (equal_distance > 1)
{
*(++begin) = *(range_end++);
}
else
{
++begin;
++range_end;
}
}
}
return ++begin;
}
