Проблема заключается в следующем. Мне нужна функция, которая, учитывая список и максимальное количество вхождений «x», удаляет все элементы списка, которые появляются более x раз или x раз.
Я нашел довольно простое решение, которое заключается в проверке каждого из элементов. При этом повторение функций поиска и удаления много раз кажется мне не оптимальным с точки зрения вычислений.
Мне было интересно, можете ли вы предоставить лучший алгоритм (я исключил выделение памяти для матрицы от минимума до максимума... слишком много для задачи... скажем, у вас мало очень больших чисел, и ваша память не подойдет это.)
Мой код следует.
typedef struct n_s
{
int val;
struct n_s *next;
}
n_t;
// deletes all elements equal to del in list with head h
n_t * delete(n_t *h, int del);
// returns the first occurrence of find in list with head h, otherwise gives NULL
n_t * find(n_t *h, int find);
n_t *
delFromList(n_t *h, int x)
{
int val;
n_t *el, *posInter;
// empty list case
if (h == NULL)
return NULL;
// first element
val=h->val;
if ( (posInter = find(h -> next,val))
&& (find(posInter -> next, val)))
h = delete(h, val);
// loop from second element
el = h;
while (el -> next)
{
val = el -> next -> val;
// check whether you want to delete the next one,
// and then if you do so, check again on the "new" next one
if ((posInter = find(el -> next -> next, val))
&& (find(posInter -> next, val)))
el -> next = delete(el -> next, val);
// in case you did not delete the nexy node, you can move on
else
el = el -> next;
}
return h;
}
Я знаю, что el->next->next может показаться запутанным, но я считаю менее интуитивным использование таких переменных, как «следующий», «прошлый»… так что извините за головную боль.
«у вас мало очень больших чисел, и ваша память этого не сделает»: что?
Можно ли изменить определение списка? Если да, у вас может быть третье поле, которое отслеживает время, когда значение «появляется» в списке. Это означало бы, что вам придется полностью изменить всю вашу программу.
Не лучшая идея объявлять массив из 100000 номеров, когда в вашем списке есть 0, 1, 2 и 99999 @YvesDaoust. Наверное, я должен был использовать пример
В силу логической необходимости при изучении элемента в списке и принятии решения о том, сохранить его или удалить, вам необходимо знать, является ли он дубликатом или нет. Учитывая только связанный список, единственный способ сделать это — выполнить поиск по списку. И, таким образом, время операции составляет O (n) на элемент, а элементов n, так что это O (n ^ 2). Однако мы можем создать дополнительные данные, например прочитать список и подготовить отсортированную копию (O(n log n)), а затем пройтись по списку, используя поиск в отсортированной копии O(log n), чтобы определить, является ли каждый элемент дубликат (всего O (n log n)).
@YvesDaoust: диапазон значений данных настолько велик, что им не хватает памяти для массива, индексированного по значению данных.
«Плохая идея...»: на самом деле, никто даже не подумал бы об этом. (Вы даже не сказали, что ваши ключи натуральные.)
Это задание класса @EricPostpischil, но у меня нет особых ограничений, кроме использования экзотических библиотек. Мне просто было интересно, могу ли я упростить или улучшить вычислительное решение.
Что за задание? Чтобы выполнить задание по дедупликации или оптимизировать время вычислений задания по дедупликации?
@YvesDaous, почему лучше использовать curr и succ? Я не очень понимаю практику. вам нужно управлять большим количеством переменных... для меня это только делает код более запутанным и подверженным ошибкам
Работа состоит в том, чтобы сделать это. Но из любопытства я тоже пытался его оптимизировать... Я пишу код не для класса, а для улучшения своих навыков.
Ну, насколько я вижу, у него нет проблем с управлением целыми числами @YvesDaoust.
Один из вариантов алгоритма с улучшенной производительностью:
D
с двумя элементами, один для значения элемента списка и один для подсчета количества его появления.D
, скопировав элемент значения из элемента списка и установив его счетчик равным единице. Если он присутствует в дереве, увеличивает его счетчик. Если его количество равно порогу или превышает его, удалите его из списка.Поиски и вставки в сбалансированном дереве выполняются за O(log n). Связанный список из n элементов использует n из них, а удаление из связанного списка — O(1). Таким образом, общее время равно O(n log n).
Используйте карту подсчета, чтобы подсчитать, сколько раз появляется каждый элемент. Ключи — это элементы, а значения — счетчики.
Затем просмотрите свой массив во второй раз, удалив все, что соответствует вашему порогу.
O(n) времени, O(n) дополнительного пространства.
Для карты требуется либо более O(n) времени (более O(1) на элемент для n элементов), либо O(r) пространства, где r — это диапазон элементов, а не их количество.
@EricPostpischil Это относится к возможности того, что хэш-функция производит большое количество коллизий относительно количества различных входных данных?
@EricPostpischil В любом случае, я не понимаю, почему диапазон элементов имеет значение. Карта, которая имеет два очень далеких друг от друга элемента, не обязательно должна быть массивной.
Если у вас нет памяти O(r) для карты, могут быть коллизии, и вам нужно как-то управлять ими, а это невозможно сделать за время O(1) на коллизию.
@EricPostpischil Я должен придерживаться своего ответа. На вероятность коллизий влияет количество хэшируемых уникальных элементов и пространство, используемое картой, но не диапазон хешируемых элементов. Например, скажем, у нас есть два набора вещей для хеширования. Набор «A» имеет {1, 10 ^ 100}, а набор «B» содержит все целые числа от 1 до 100. Для карты одинакового размера у B гораздо больше шансов столкнуться с коллизиями, чем у A.
Вы можете заявить, что ваш алгоритм имеет хорошую производительность в некоторых подмножествах случаев. Но обозначение «О» означает, что ограничение применяется ко всем случаям. Утверждение, что алгоритм использует время O(n) с пространством O(n), неверно.
@EricPostpischil В Википедии указано O(n) пробел: en.wikipedia.org/wiki/Hash_table, CLRS Intro to Algorithms говорит O(n) пробел (2-е изд., глава 11.2 «Хеш-таблицы»).
Да, хеш - это пространство O (n). Это не время O (n), как неправильно говорит этот ответ. Как говорится в моем комментарии, карта либо требует больше, чем O (n) времени, либо требует O (r) места. Заявление о том, что решение карты равно O (n) времени и O (n) пространству, неверно.
@EricPostpischil Вы были бы удовлетворены, если бы я добавил слово «ожидаемый» - ожидаемое время O (n), поскольку все хеш-операции ожидаются за время O (1)? Я до сих пор не знаю, откуда вы получаете O(r) — диапазон не имеет значения.
Вы должны указать контекст для этого. Если это задание для класса, обычно существуют либо ограничения, которые необходимо соблюдать, либо контекст для извлеченного урока, который указывает, какие решения следует использовать. Если это проблема реального мира, то следует задаться вопросом, почему вы используете для этого связанный список и какие альтернативные или дополнительные структуры данных мы можем рассмотреть.