我的“从无序链表中删除重复项”的代码超出了大量节点链表的时间

Question

我想要一种替代方法来在时间约束内解决链表中大量节点的给定问题：

1 <= T <= 100

1 <= N <= 10 ^ 4

1 <= data <= 10 ^ 5

我正在使用STL的地图数据结构。如果节点未被访问（意味着它存储在地图中的

node->data

不等于 true），我会更新地图并使其

node->data

等于 true。如果存在，我会删除该节点。

这对于较少数量的节点来说效果很好。但如果节点较多，就会超出时间限制。 建议我替代方法。

Node *removeDuplicates(Node* &head)
 {

// if only has one node
if (head == nullptr || head->next == nullptr)
{
    return head;
}

Node * curr = head;
Node * prev = nullptr;
map<int , bool> myMap;
while(curr != nullptr){
   
    if(myMap[curr->data] == true){
        Node * nodeToDelete = curr;
        curr = curr->next;
        prev->next = curr;
        delete(nodeToDelete);
    }
    else{
        myMap[curr->data] = true;
        prev = curr;
        curr = curr->next;
    }
}
return head;
}

Answer 1

如果使用布尔数组作为查找表来记录节点是否已被访问，您将获得尽可能快的运行时间。数组的大小约为 100KB。

// Initialize lookup table
bool visited[10^5];
memset(visited, 0, 10^5);

Node * curr = head;
Node * prev = nullptr;
map<int , bool> myMap;
while (curr != nullptr)
{
    if (visited[curr->data] == true)
    {
        Node * nodeToDelete = curr;
        curr = curr->next;
        prev->next = curr;
        delete(nodeToDelete);
    }
    else
    {
        visited[curr->data] = true;
        prev = curr;
        curr = curr->next;
    }
}