題目:有兩個表,有一個相同的字段,現在要選出這兩個字段相同的記錄,除了用兩重循環之外,還有什麼辦法?(某面試題)
這個問題,其實有很多不明確的地方,但就題目本身而言,很明顯,當前復雜度是O(n2),如果解答不能講這個復雜度降低的話,就根本不算什麼優化。這裡假定,選擇一條 記錄的復雜度為O(1)。
各位大神,請問你們有什麼辦法呢?可以考慮各種實現,把你們的思想曬出來。。。
如果是循環鏈表的話,時間復雜度為1,因為循環鏈表的一個指針可以直接知道它的前節點和後節點,只需要兩個循環鏈表的指針指向的各自的節點斷開,然後鏈接起來就可以了。
如果是單鏈表的話,時間復雜度為n,因為兩個單鏈表只能首尾鏈接,所以其中一個鏈表的指針需要循環n次,才能查找到它的尾指針,然後與另外一個指針相連。
如果內外循環之間的循環量之間沒關系可將內外循環次數之積作為復雜度看待,若有關系則考慮內循環的基本操作的執行次數來分析復雜度