搜索與大O時間限制

對於分配重複，我要創建一個構造函數取一個String [] 名和int [] 排名爲完成以下任務O參數（N日誌N ）：搜索與大O時間限制

（數據驗證）：

檢查該名稱和秩具有相同的長度---（時間：O（1））
檢查這兩個名和排名不是空---（時間：O（1））
將檢查不包含任何重複或空字符串名字---（時間：O（n^2））???

檢查該秩僅包含不同元件的---（時間：???）

（實際對象declarance）：

添加的名稱和每個索引值等級到自定義類型的ArrayList（時間：O（n））

對於該項目，我不允許使用數組和ArrayLists之外的任何數據結構（無Map或Set接口），但我可以使用Arrays類中的方法來搜索和排序數組。我沒有看到如何在O（n log n）時間完成所有這些事情。我特別不知道如何在小於O（n^2）的時間內完成第3步。謝謝您的幫助！

來源

2014-02-26 zZShort_CircuitZz

步驟1 & 2是微不足道的。

第3步：

排序與 =>O(n log n)
迭代數組檢查每個條目與下一個在陣列（看到，如果你發現一個重複的）=>O(n)

==>總共= O (n log n)

步驟4：相同的方法

來源

2014-02-26 03:05:07 assylias

感謝您的回覆！有一個排序的數組意味着我只需要將名稱[i]與名稱[i + 1]，名稱[i + 1]與名稱[i + 2]進行比較，等等。之前沒有想過這個。 –

搜索與大O時間限制

回答

相關問題