2019年8月3日，网易校招 算法工程师岗位 大题第一道

刚才笔试，一道题没做出来， 第一道题，写出来了，时间复杂度还太大，测试超时了。很不甘心，于是交卷后又重新思考了一下。其实很简单

题目：有一天，小易把1到n的所有排列按字典序列排成一排。小易从中选出了一个排列，假设它是正数第Q个排列，小易希望你能回答他倒数第Q个排列是什么。

例如1到3的所有排列是：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

若小易选出的排列是 1 2 3 ，则Q=1，而你应该输出排列3 2 1

输入描述：

第一行数字n，表示排列长度接下来一行n个数字，表示选出的排列1<= n <= 300000

输出描述：

一行n个数字，表示所求的排列。

示例1：

输入

3
1 2 3

输出：

3 2 1

示例2：

输入

5
3 1 5 2 4

输出：

3 5 1 4 2

方法一：

这是我笔试时写的。如果按照题目的思路，你需要先知道所有排列的可能性，然后安装索引Q输出。

也就是

1捕获输入；

2对所给输入进行排序，把3 1 5 2 4 重新排序成 1 2 3 4 5  ，12345也是所有排列组合的第一种

3 罗列所有排列组合的可能性，12345、12354、12435、12453这种

4计算Q，你要知道3 1 5 2 4 是所有排列组合中的第几种，这里Q是第53，索引是52.

5输出结果，然后输出【所有排列可能性】中倒数第53个

这里插一句，在线笔试题用的牛客网，编程时是可以切换页面的。我们不妨把输入功能写成通用的方法，存放在自己的工具包中，下次使用，直接粘贴，很方面。（用我GitHub上代码时能不能点个星）

下面是python代码。完全可以不用看，直接看方法2

# https://github.com/zihaozhang9/utils/blob/master/OnlineExam.py
 
def decIn(Str_in):
    line = Str_in.strip().split()
    try:
        line = [int(i) for i in line]
    except:
        print('input error')
        exit()
    return line
def read1(chang):
    tmp = decIn(input())
    while len(tmp)<chang:
        tmp = decIn(input())
    return tmp
    
def swap(t1, t2):
    return t2, t1
 
#读取输入
n = read1(1)[0]
line1 = read1(1)
linesort = line1.copy()
linesort.sort()
 
#获取所有排列组合情况
lines = []
while True:
    lines.append(linesort.copy())
    j = n-2
    while linesort[j]>=linesort[j+1]:
        j = j-1
    if j<0: break
    
    k = n -1 
    while (k>j)and(linesort[k]<=linesort[j]):
        k = k-1
    linesort[k],linesort[j]=swap(linesort[k],linesort[j])
    
    l = j+1
    r = n-1
    while l<r:
        linesort[l],linesort[r]=swap(linesort[l],linesort[r])
        l = l+1
        r = r-1
#计算Q
Q=0
for idx,i in enumerate(lines):
    if line1 == i:
        Q = idx
        break
#给出倒数第Q的结果
Q=Q+1
for i in lines[-Q]:
    print(i,end=' ')  

结果当然是可以运行， 但时间复杂度太高，测试用例只通过40%。

方法二，五行代码

可以将所有的排列组合看成一种树结构。【第Q中排列】和【倒数第Q种】排列其实是对称的。我们不需要知道所有的排列组合情况，我们只需要根据当前顺序对称过去就好了。



代码-核心代码其实就5行。不过这是考完之后想到的，没测试过，不一定对。

def decIn(Str_in):
    line = Str_in.strip().split()
    try:
        line = [int(i) for i in line]
    except:
        print('input error')
        exit()
    return line
def read1(chang):
    tmp = decIn(input())
    while len(tmp)<chang:
        tmp = decIn(input())
    return tmp
    
n = read1(1)[0]
line_in = read1(1)
linesort = line_in.copy()
linesort.sort()
#或得到对称的元素
def getflip(line,e):
    idx = line.index(e)+1
    return line[-idx]
#直接打印结果
for e in line_in:
    print( getflip(linesort,e), end=' ')

#网易##笔试题目##校招#