网易20届提前批笔试第一题：字典序排列
其实这题就是在考字典序全排列，然后计算出总的排列数(n的阶乘)，倒数第Q个排列即为正数(n!-Q+1)个排列，但是注意在python中的index是从0开始的。
所以当找到给定排列的位置idx后，倒数第Q个排列的位置是：(n!-(idx+1)+1)-1 = n!-idx-1
考试的时候傻了，用一个list去储存所有的排列，其实根本不需要的。
真的傻了傻了。
def permute(nums, n, total):
cnt = 0
idx = 0
while True:
try:
if nums == myinput:
idx = cnt
low_index = n-1
while low_index > 0 and nums[low_index-1] > nums[low_index]:
low_index -= 1
if low_index == 0:
break
low_index -= 1
high_index = low_index + 1
while high_index < n and nums[high_index] > nums[low_index]:
high_index += 1
high_index -= 1
nums[low_index], nums[high_index] = nums[high_index], nums[low_index]
nums[low_index+1:] = reversed(nums[low_index+1:])
cnt += 1
if cnt == total - idx - 1:
return nums
except:
break
if __name__ == '__main__':
n = int(input())
myinput = list(map(int, input().split()))
# res_list = func(n, myinput)
total = 1
for i in range(1, n + 1):
total = total * i
nums = list(range(1, n + 1))
nums.sort()
res_list = permute(nums, n, total)
for i in range(len(res_list)):
res_list[i] = str(res_list[i])
print(' '.join(res_list))
上海得物信息集团有限公司公司福利 1166人发布