algorithm - 将名称排序列表转换为等级排序列表

  显示原文与译文双语对照的内容
0 0

这是一个面试问题。

提供一个最佳解决方案来实现这里目的:
按名称排序的学生记录的: 列表。
按年级排序:学生记录列表,按等级排序,按名称排序
等级可以是'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 

我提出了这个解决方案:

  1. 将列表插入到地图中
  2. 哈希映射有 5个桶,每个级别一个
  3. 将学生同一年级的学生分成一个。
  4. 链接用于管理冲突
  5. 为了避免插入 O(n2) 复杂性,我存储了最后一个节点指针,实现了 O(1) 随机插入复杂性。

我的问题是我的解决方案是否正确?
如果是,可以改进什么?
如果没有,还可以使用什么其他数据结构来实现这里?

时间: 原作者:

0 0

你的方法是 O(n) 时间,带有 O(n) 额外空间,基本上是 Bucket排序的变种。

在时间复杂性方面,这是最好的渐进复杂性,因为输出大小本身是 O(n)

注意,实际上不需要哈希映射,只能有链接列表的array,它的中级别映射到 array,等等。


然而,一个小的优化实际上是一个交易:

你可以使用 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) 时间- - 这里不是一个自由午餐。

原作者:
...