这题就是回答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)一定不对 : 他很肯定说这样做答案绝对不是线性的 : 想请问这样计算时间复杂度到底哪里有问题 : 谢谢 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 100.8.92.201 (美国) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1629166141.A.517.html ※ 编辑: wawi2 (100.8.92.201 美国), 08/17/2021 10:10:59