這題就是回答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/m.aspx?n=bbs/Soft_Job/M.1629166141.A.517.html ※ 編輯: wawi2 (100.8.92.201 美國), 08/17/2021 10:10:59