数据结构Python版练习题（一）

本文主要是介绍数据结构Python版练习题（一），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

 解题代码：

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))

这篇关于数据结构Python版练习题（一）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！