请教一道算法题

Job Hunting Interview
, , , , , ,
1

给两个string list,return string that is only in one of the list.
比如a = [‘a’,‘b’,‘c’,‘d’] b = [‘b’,‘e’] return = [‘a’,‘c’,‘e’]

这题的最优解是什么？ 我能想出来的就是搞两个set 然后进行筛选

2

这题本质上就是 intersection of two arrays
可以用set，也可以sort以后用两个pointer或者binary search，三种解法各有利弊

参考

3

我怎么没看懂 字母d为啥不在答案里面

4

a = [‘a’,‘b’,‘c’,‘d’] b = [‘b’,‘e’] 的 intersection 是 [‘b’] ，它的补集 就是 [‘a’,‘c’,‘e’, ‘d’]
lz可能少写了d

5

那建个大map直接计数不行么 最后只返回value=1的

6

这样空间很浪费

7

好吧 感觉时空本来就是一对矛盾 要看具体要求了

8

但如果要浪费空间的话，也会用HashSet，而不是 Map

9

排序需要的时间复杂度怎么说

10

假设size为m和n, m >> n, 那么binary search是 O(n*log(m))
排序本身要 nlog(n) + mlog(m)