刚刚编辑文章按到复原草稿 插入很多不必要东西 但用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), 来自: 114.24.250.114 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Soft_Job/M.1629135646.A.93D.html