贊助廠商

娛樂城推薦

首頁

商業與財經/工作與就業/其他:工作與就業列表

軟體人- 面試白板考題目的時間複雜度 面試白板考題目的時間複雜度

幫以前社團認識的學妹代po我是今年畢業的新鮮人今天面試白板考的時候考了跟差集有關的問題關於時間複雜度的部分怎麼想都想不通已經查過資料也跟要考資工所的朋友、資工系的朋友討論過仍然不確定答案,想請版上大神開示一下:D題目:有A、B兩個未經排序的arrayA有n個整數,B有m個整數寫一個function回傳在A且不在B的整數。(皆先不討論A、B內各自有重複元素的情況)我的做法:1.先把B的每個元素放進dictionary2.然後用for檢查A的每個元素是否為dictionary的key,不是的話就加入ans的list3.回傳ans想以python的dictionary來討論這題的時間複雜度用B建立長度為m的dictionary新增一組key-value時間複雜度是O(1);A的長度為n查找是否在dictionary的key時的時間複雜度是O(1)我覺得時間複雜度是O(m+n)。參考leetcode簡中板的類似題目的官方詳解(只有簡中版討論區有官方詳解)https://reurl.cc/KAaRmyleetcode這題基本一樣是找出在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的時間複雜度!謝謝指教--
  • 發問日期:2021-08-17 02:00:02

友站連結