在 C++ 中使用映射解决 "Removing duplicates from unsorted linked list" 时的 TLE

Question

我正在尝试使用地图解决 GFG 上的 removing duplicates from unsorted linked list 问题。我已经使用插入和查找命令找到了可接受的解决方案：

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;
}

Answer 1

第二个解决方案存在多个问题。

你的运行通过链表两次，如果可能的话不要这样做。
unordered_map 可能会快得多，正如评论中已经提到的
你在第二个解决方案中寻找更多的重复项，3 对 2。

以上任何一种都可能进一步导致缓存拥塞，进一步降低速度。

在 C++ 中使用映射解决 "Removing duplicates from unsorted linked list" 时的 TLE

TLE when solving "Removing duplicates from unsorted linked list" using maps in c++

algorithm

linked-list

c++14