C++用map实现无序链表去重时第二种写法出现TLE问题求解

1. 链表遍历次数翻倍 #

第一种写法仅做1次链表遍历，边遍历边判断去重、删除重复节点；第二种写法需要完整遍历2次链表：第一次统计所有出现过的元素，第二次执行删除操作。当测试用例的链表长度极大时，遍历开销直接翻倍。

2. std::map操作开销远高于第一种写法 #

C++的std::map底层为红黑树，单次查找/插入操作复杂度为O(logK)（K为不同元素的数量），两种写法的map操作开销差异如下：

• 第一种写法仅对每个元素执行1次find操作，仅首次出现的元素额外执行1次insert操作，总map操作次数等于链表长度N。且find仅做查找，不会产生额外插入开销。
• 第二种写法的map操作次数是第一种的3倍：
  • 第一次遍历每个元素都调用operator[]做赋值操作，哪怕是重复出现的元素，也会触发O(logK)的查找+赋值逻辑，产生无意义的开销；
  • 第二次遍历每个元素时，会先后两次调用operator[]（一次做值判断，一次修改为0），且operator[]在键不存在时会自动插入默认值（int类型默认是0），进一步增加了不必要的插入开销。

两种因素叠加后，第二种写法的总时间复杂度虽然和第一种同属O(NlogN)级别，但常数项是第一种的数倍，大数据量测试用例下就会触发超时。

内容的提问来源于stack exchange，提问作者Nightwing1914