first unique string有可能一遍扫描吗？

看到一个题非常类似Leetcode的387. First Unique Character in a String，只不过把输入变成array of string，要求返回first unique string。用hashtable可以O(n)，先扫一遍建hashtable，然后再扫一遍找第一个unique的。但是要求O(n)而不是O(2n)，这个可能吗？

O(n)和O(2n)有啥区别……请正确使用big-O notation

可能，用额外空间

弱弱问用trie算一遍扫描吗

用两个hashmap，第一个是freq:words, 第二个是word:freq, 一遍扫过去，更新两个hashmap, 难点在于你要找一个能够在O(1)的时间里定位并删除的能够保持输入顺序数据结构去装第一个hashmap里的words，这个可以参考LRU那道题的做法，我觉得这点要麻烦一点，因为我一时想不到一个已有的数据结构可以用，要自己写

用一个hashmap和一个linklist，hashmap里面存放link node及其出现次数，linklist中始终只保留出现次数为1的string node，一边扫一边删，注意保留好头指针，最后剩下的这个list就是所有的unique string，而list的头就是第一个unique string。

python就是OrderedDict，然后输出第一个

别的大多语言就得自己实现了，基本就多用一个个double linked list吧

cai_lw 发表于 2018-3-15 12:03
O(n)和O(2n)有啥区别……请正确使用big-O notation

他们就是这么写的。是不严谨，但是大家知道什么意思就好了，呵呵。