360公司 重排序列 python

360 重排序列 python

2022.09.09

题目描述

给定一个长度为N的序列A₁到A_N，现在要对序列进行M次操作，每次操作对序列的前若干项进行升序或降序排列,求经过这M次操作后得到的序列。

输入描述

第一行包含两个整数N和M,1 $\le$ N, M $\le$ 105.
第二行包含N个空格隔开的整数A₁到A_N, 1 $\le$ A $\le$ 10⁹.
接下来M行,每行包含两个整数t和x，0 $\le$ 1,1 $\le$ x $\le$ N,若t=0,则表示对A₁到A_N,进行升序排列;若t=1,则表示对A₁到A_N进行降序排列。操作执行顺序与输入顺序一致。

输出描述

输出N个空格隔开的整数,即经过M次操作后得到的序列

样例输入

4 2
1 2 4 3
1 3
0 2
1
2
3
4

样例揄出

2 4 1 3
1

解题思路

• sort 与 sorted 区别：
  sort 是应用在 list 上的方法，sorted 可以对所有可迭代的对象进行排序操作。
  list 的 sort 方法返回的是对已经存在的列表进行操作，无返回值，而内建函数 sorted 方法返回的是一个新的 list，而不是在原来的基础上进行的操作。

# sort()
list1 = [1,2,4,3]
print(list1[0:3].sort())
#输出为None
---------------------------------------
# sorted()
list1 = [1,4,2,3]
print(sorted(list1[0:3]))
#输出为[1, 2, 4]
1
2
3
4
5
6
7
8
9

在对列表进行区间排序之后，不在区间的元素会被舍弃，为了保存列表的完整性，需要对舍弃的元素先保存。

list1 = [1,2,4,3]
list2 = list1[3:] # 把舍弃的元素在排序之前先保存一下
print(sorted(list1[0:3],reverse=True)+list2) # 前3个元素降序排列
#输出为[4, 2, 1, 3] # 前3个元素降序排列
1
2
3
4

n,m = map(int,input().split())
list1 = list(map(int,input().split())) # 输入列表
while m:
    t,x = map(int,input().split())
    if t==0: # t为0，升序
        list2 = list1[x:]# 对后x个元素保存
        list1 = sorted(list1[0:x]) + list2# 升序
        m-=1
    else:
        list2 = list1[x:]
        list1 = sorted(list1[0:x],reverse=True)+list2# 降序
        m-=1
for i in list1:
    print(i,end=' ') # 以空格为间隔进行输出
1
2
3
4
5
6
7
8
9
10
11
12
13
14