將名稱有序列表轉換爲有序列表

Question

這是一個面試問題。

提供最佳的解決方案來實現這一目標：
輸入：學生檔案，按名稱排序列表。
輸出：學生檔案表，按等級進行排序，然後按名稱
級可以 'A'， 'B'， 'C'， 'd'， 'E'

樣品輸入

Name | Grade 
Adam | B 
Ashley | C 
Boxer | A 
Britney | A 
Caroline | E 
David | B 

樣本輸出

Name | Grade 
Boxer | A 
Britney | A 
Adam | B 
David | B 
Ashley | C 
Caroline | E 

我提出這個SOLU重刑：

1. 插入列表轉換爲具有地圖
2. 散列的地圖有5個桶，每個年級一個
3. 插入學生共享同一年級到一個桶裏。
4. 鏈接用於管理碰撞
5. 爲了避免O(n2)用於插入的複雜性，我存儲在桶中，其實現O(1)隨機插入複雜的最後一個節點的指針。

我的問題是我的解決方案是否正確？
如果是，有什麼可以改進的？
如果不是，還有什麼其他的數據結構可以用來實現這一點？

Answer 1

你的方法是O(n)時間，O(n)額外的空間，基本上是Bucket Sort（並可能是面試官想聽到的）的變化。

就時間複雜度而言 - 這是您可以實現的最佳漸近複雜度，因爲輸出大小本身是O(n)。

請注意，您實際上不需要哈希映射，您可以擁有一個鏈接列表數組，其中A級映射到數組的第一個條目，B級映射到第二個條目，依此類推。 。

---

然而，一個小小的優化實際上是一種權衡：

你可以有O(n)時間O(1)空間 - 由每可能年級迭代一次有你的時間更糟糕的常數：

for each grade (descending order): 
    for each student in list: 
     if student.grade == grade: 
      print student 

這將是O(G*n)時間，其中G是可能的等級的數量，但由於它在這裏是一個常數 - 它衰減到O(n)時間，O(1)空間，但如上所述 - 它不是免費的午餐 - 常量很多這裏更糟糕。