Блог

Главная - Вопросы по программированию - TLE при решении проблемы «Удаление дубликатов из несортированного связанного списка» с использованием карт в c

TLE при решении проблемы «Удаление дубликатов из несортированного связанного списка» с использованием карт в c

#algorithm #linked-list #c 14

Вопрос:

Я пытаюсь решить проблему удаления дубликатов из несортированного связанного списка в GFG с помощью карт. Я выяснил принятое решение, используя команды insert и find:

 Node * removeDuplicates( Node *head) 
{
 // your code goes here
 map <int, int> duplicates;
 
 Node* curr=head;
 Node* prev=NULL;
 while(curr){
     
     if(duplicates.find(curr->data)==duplicates.end()){
         duplicates.insert({curr->data,1});
         prev=curr;
         
     }
     else{
         
         prev->next=curr->next;
         delete(curr);
     }
     curr=prev->next;
 }
 return head;
}

Но другой подход, который я пробовал ранее, — это предоставление TLE для отправки, хотя он отлично работает, например, в тестовом примере. Я попытался реализовать ту же идею, что и выше, но немного по-другому. Кто-нибудь может мне помочь с этим?

 Node * removeDuplicates( Node *head) 
{
 map <int, int> duplicates;
 Node* temp=head;
 while(temp){
     duplicates[temp->data]=1;
     temp=temp->next;
 }
 
 Node* curr=head;
 Node* prev=NULL;
 while(curr){
     
     if(duplicates[curr->data]==1){
         duplicates[curr->data]=0;
         prev=curr;
         
     }
     else{
         
         prev->next=curr->next;
         delete(curr);
     }
     curr=prev->next;
 }
 return head;
}

Комментарии:

1. Для непосвященных, что такое TLE?

2. Первое, что нужно попробовать, — это unordered_map вместо карты. unordered_set должен быть еще лучше.

3. @Steftle = Превышен Лимит Времени. В алгоритмических задачах это означает, что решение работает слишком долго для некоторого тестового случая, соответствующего ограничениям.

Ответ №1:

Со 2-м решением существует множество проблем.

  • если вы дважды просматриваете связанный список, не делайте этого, если это возможно.
  • unordered_map может быть намного быстрее, как уже упоминалось в комментариях
  • вы больше смотрите на дубликаты во 2-м решении, 3 против 2.

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

Метки: