解题代码:
a = int(input()) b = [] c = [] i = 0 while i < a: # 先输入成绩,分别存入班级列表以及成绩列表 # print(i) num = [int(n) for n in input().split()] b.append(num[0]) c.append(num[1]) i += 1 q1 = [] q2 = [] a = int(input()) i = 0 while i < a: # 再输入问题 num = [int(n) for n in input().split()] q1.append(num[0]) q2.append(num[1]) i += 1 i = 0 e = [] f = [] g = [] while i < a: cls = q1[i] j = 0 while j < len(b): if b[j] == cls: e.append(c[j]) f.append(j) j += 1 for k in e: g.append(k) e.sort(reverse=True) index = g.index(e[q2[i] - 1]) print(f[index] + 1) i += 1 e.clear() f.clear() g.clear()
解题思路分析:
假设输入是
6
1 5
1 2
1 8
2 3
2 9
3 1
4
1 2
1 3
2 2
3 1
首先使用两个列表b、c来存储成绩数据,b[i]中存储班级信息,则对应的c[i]中存储成绩信息。即b = [1, 1, 1, 2, 2, 3],c = [5, 2, 8, 3, 9, 1]。
之后再使用两个列表q1以及q2来存储老师的提问,其中q1[i]中存储的老师第i个提问中的班级信息,q2[i]表示对应的在班级中的排名。即q1 = [1, 1, 2, 3],q2 = [2, 3, 2, 1]。之后会用q1[0]以及q2[0]举例。
之后,对于提问列表进行处理:
1. 每次从q1中依顺序取出一个数据,表示班级,例如1。
2. 在b中进行查找,如果b[j]等于1,则将c[j]添加到列表e中,即e是班级为1的班级中所有学生的成绩列表。将j添加到列表f,即f是班级1的学生在输入中的位置列表。e与f是一一对应的关系。
3. 新建列表g,将e中元素依次添加到g中,形成e的副本。此时g = [5, 2, 8],e = [8, 5, 2],f = [0, 1, 2]。
4. 对e按照从大到小排序,之后可以按索引直接找到对应排名的成绩,如排名第2的成绩就是5.
5. 之后根据排名在g中寻找索引,索引是0,则f[0]就是该学生在列表b中的索引,此时,只需要将其加1即可得到他在输入中的位置顺序。问题得到解决。
复杂度分析:
时间复杂度:假设问题数为m,学生人数是n,则根据以下循环:
while i < a:
cls = q1[i]
j = 0
while j < len(b):
if b[j] == cls:
e.append(c[j])
f.append(j)
j += 1
可得时间复杂度为O(m*n)
采用了两个列表存储问题,两个列表存储学生成绩。则空间复杂度为:
O(max(m,n))