幫以前社團認識的學妹代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的時間複雜度！ 謝謝指教 --
