編程挑戰賽典花費過多時間

我寫了下面的代碼爲this problem.編程挑戰賽典花費過多時間

prof = sorted([int(input()) for x in range(int(input()))]) 
student = sorted([int(input()) for x in range(int(input()))]) 

prof_dates = len(prof) 
stud_dates = len(student) 

amount = 0 

prof_index = 0 
stud_index = 0 

while stud_index < stud_dates and prof_index < prof_dates: 
    if student[stud_index] == prof[prof_index]: 
     amount += 1 
     stud_index += 1 

    elif student[stud_index] > prof[prof_index]: 
     prof_index += 1 

    elif student[stud_index] < prof[prof_index]: 
     stud_index += 1 


print(amount)

但代碼生成一個時間超出限制錯誤。之前我曾嘗試在學生中爲每個項目使用in，但它產生了TLE，我相信這是因爲in聲明是O(n)。所以，我寫了這段代碼，其步驟要求大致等於兩個列表長度的總和。但是這也產生了一個TLE。所以，我應該在我的代碼中做出什麼樣的改變。有一些特定的部分有很高的時間開銷嗎？

謝謝。

來源

2016-04-29 Some Name

爲什麼downvote時，下面的代碼解決了O(M + N)問題？ –

由於代碼正在工作，這可能更適合[codereview.se]。 – usr2564301

您正在使用排序+合併。這需要O(NlogN + MlogM + N + M)時間複雜度。

但你可以把教授的數據在set，檢查每一個學生一年值（從未排序列表）並獲得O(M + N)複雜度（平均）。

請注意，此方法消除了學生列表排序的長時間操作。

此外：python有內置集合。對於沒有這種規定的語言，教授的列表已經排序，所以您可以每年使用二進制搜索。複雜性將是O(NlogM)。

來源

2016-04-29 11:45:45 MBo

因爲只有一個包含檢查是必要的，所以一組將是更好的選擇。 – PKuhn

但'set'刪除重複的項目。我們必須計算重複項目。 –

@Some Name按照我的說法，僅使用prof數據進行設置。所以你會把所有的學生數據都重複一遍。而且你不應該關心教授名單中的重複，他們不打擾。 – MBo

由於問題主要是要找到兩個整數集合的交集假設一本字典的訪問是可能的O(1)

prof = set([int(input()) for x in range(int(input()))]) 
student = set([int(input()) for x in range(int(input()))]) 

equals_dates = len(prof.intersection(student))

來源

2016-04-29 11:53:30 PKuhn

但'set'刪除重複的項目。我們必須計算重複項目。 –

編程挑戰賽典花費過多時間

回答

相關問題