c++ - 使用散列从链表中删除重复项

Question

我尝试使用散列从链接列表中删除重复项。不是使用unordered_map，而是使用 vector 来跟踪出现的情况。我运行了一个简单的测试用例，但得到了我不明白的结果。 我的代码是:

class Solution {
   public:
         Node* removeDuplicates(Node *head) {
             vector<int> vec{10000 , 0};
             auto tmp = head;
             auto tmp2 = tmp;
             while (tmp) {
                 vec[tmp->data]++;
                 cout << "Data : " << tmp->data << " counter " << vec[tmp->data] << "\n";
                 if (vec[tmp->data] > 1) {                     
                     tmp2->next = tmp2->next->next;
                 }
                 tmp2 = tmp;
                 tmp = tmp->next;
             }
             return head;
         }

我尝试了以下测试用例 2 3 3 4 6. 这是链表中节点的数据。

我得到的结果是这样的。

Data : 2 counter 1
Data : 3 counter 1
Data : 3 counter 2
Data : 4 counter 1
Data : 6 counter 4114

2 3 4 

实际结果应该是

Data : 2 counter 1
Data : 3 counter 1
Data : 3 counter 2
Data : 4 counter 1
Data : 6 counter 1

2 3 4 6

Answer 1

vector<int> vec{10000, 0};创建一个包含两个元素的 vector 10000和0 ，使用采用 std::initializer_list 的构造函数:

vector(std::initializer_list<T> init, const Allocator& alloc = Allocator());

您很可能需要vector<int> vec(10000, 0); 。这将创建一个包含 10000 个元素的 vector ，初始化为 0 ，使用

vector(size_type count, const T& value, const Allocator& alloc = Allocator());

标准reads [over.match.list] :

When objects of non-aggregate class type T are list-initialized such that [dcl.init.list] specifies that overload resolution is performed according to the rules in this subclause, overload resolution selects the constructor in two phases:

• Initially, the candidate functions are the initializer-list constructors ([dcl.init.list]) of the class T and the argument list consists of the initializer list as a single argument.
• If no viable initializer-list constructor is found, overload resolution is performed again, where the candidate functions are all the constructors of the class T and the argument list consists of the elements of the initializer list.