这题就是回答O(m+n)
面试官硬说不是线性 大概有以下几种可能
1. 面试官搞错order map跟unordered map了
2. 面试官想追问worst case的话 hash table的search复杂度就不是O(1)
这样你的答案就不是O(m+n)
1的情形是面试官颗颗
2的情形可能是沟通误会
可能是面试官没有明确说 what if collision happens very frequently?
也可能是你朋友没有理解面试官其实想问collision之后的chaining的结果
不过既然你朋友知道红黑树这东西
没道理不知道红黑树是为了解决hash的collision问题
所以我猜是面试官自己搞错了
但是不管1或2 都是move on就好 不用纠结在实作上的特性
你就想想 如果你遇到这种同事 你会想跟他一起工作吗?
※ 引述《cccict (马路柏油)》之铭言：
: 刚刚编辑文章按到复原草稿
: 插入很多不必要东西
: 但用Pitt没办法编辑
: 所以删除重po不好意思
: 以下代之前社团认识的学妹代po询问
: 我是今年毕业的新鲜人
: 今天面试白板考的时候考了跟差集有关的问题
: 关于时间复杂度的部分怎么想都想不通
: 已经查过资料也跟要考资工所的朋友、资工系的朋友讨论过
: 仍然不确定答案，想请版上大神开示一下：D
: 题目：有A、B两个未经排序的array
: A有n个整数，B有m个整数
: 写一个function回传在A且不在B的整数。
: (皆先不讨论A、B内各自有重复元素的情况)
: 我的做法：
: 1.先把B的每个元素放进dictionary
: 2.然后用for检查A的每个元素是否为dictionary的key，不是的话就加入ans的list
: 3.回传ans
: 想以python的dictionary来讨论这题的时间复杂度
: 用B建立长度为m的dictionary
: 新增一组key-value时间复杂度是O(1)；A的长度为n
: 查找是否在dictionary的key时的时间复杂度是O(1)
: 我觉得时间复杂度是O(m+n)。
: 参考leetcode简中板的类似题目的官方详解(只有简中版讨论区有官方详解)
: https://reurl.cc/KAaRmy
: leetcode这题基本一样
: 是找出在A且在B的整数
: 官方是用set来实作
: 时间复杂度是O(m+n)
: 想请问dictionary和set()底层的hash原理会是造成时间复杂度不同的关键吗？
: Python程式码如下
: def solution(A:List[int], B:List[int]):
: ans = []
: dic = dict()
: for b in B:
: dic[b] = b
: for a in A:
: if a not in dic:
: ans.append(a)
: return ans
: 另外，我知道hash在python以外的语言像是C/C++
: 若是基于红黑树来实做的话
: 时间复杂度会是O(nlogm)。
: 我想问的是python的时间复杂度！
: 补充
: 想知道答案是因为
: 面试官说我的答案O(m+n)一定不对
: 他很肯定说这样做答案绝对不是线性的
: 想请问这样计算时间复杂度到底哪里有问题
: 谢谢