现在有一个有序的列表: [75,78,80,89,89,92,93]
需要对他们按成绩进行排名。
说到排名,一般大家会这样写:
grade_list = [75, 78, 80, 89, 89, 92, 93]
for index, grade in enumerate(grade_list, start=1): print(f'成绩:{grade},排名第:{index}')
运行效果如下图所示:
现在问题来了,由于89出现了两次,他们应该是并列第4名才对。那么就需要写一个算法,来实现并列排名。
并列排名有两种情况,第一种是两个89都是第4名,接下来的92是第5名:
# 情况一成绩:75,排名第:1成绩:78,排名第:2成绩:80,排名第:3成绩:89,排名第:4成绩:89,排名第:4成绩:92,排名第:5成绩:93,排名第:7
还有另一种情况,两个89都是第4名,接下来的92直接就是第6名,没有第5名:
# 情况二成绩:75,排名第:1成绩:78,排名第:2成绩:80,排名第:3成绩:89,排名第:4成绩:89,排名第:4成绩:92,排名第:6成绩:93,排名第:7
针对这两种情况,我们都来实现一下。
首先是情况一。
grade_list = [75, 78, 80, 89, 89, 92, 93]
current_grade = 0current_index = 0
for grade in grade_list: if grade > current_grade: current_index += 1 print(f'成绩:{grade},排名第:{current_index}') current_grade = grade
运行效果如下图所示:
接下来是情况二:
grade_list = [75, 78, 80, 89, 89, 92, 93]
current_grade = 0current_index = 0
for index, grade in enumerate(grade_list, start=1): if grade > current_grade: current_index = index print(f'成绩:{grade},排名第:{current_index}') current_grade = grade
运行效果如下图所示:
这两种写法,空间复杂度都是 O(1)
,无论有序列表有多长,我们自己申请的空间都恒定不变。由于只遍历一次列表,所以时间复杂度为 O(n)
。
经过测试,对于有序列表为空、只有一个元素、只有2个相同元素、有两个不同元素这些边界情况都能很好地兼容。