数据结构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版练习题(一)


数据结构Python版练习题(一) 

 

上一篇:poj 2446 Chessboard (二分匹配)


下一篇:Python习题《古典—兔子生兔子问题》