解题代码:
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))