欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Lintcode197 Permutation Index solution 题解

程序员文章站 2022-05-26 11:13:45
【题目描述】 Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicograp ......

【题目描述】

 

 

Given a permutation which contains no repeated number, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1.

给出一个不含重复数字的排列,求这些数字的所有排列按字典序排序后该排列的编号。其中,编号从1开始。

【题目链接】

www.lintcode.com/en/problem/permutation-index/

【题目解析】

由于本题不需要计算出所有排列,则可用排列组合的原理直接解出答案。举个例子, [2,3,1,4]共有4!种排列方法,答案要求是从[1,2,3,4]按字典排序至[2,3,1,4]有多少种排法。在每确定一位的情况下剩余的所有排法为(n-i)!,即在第1位2确定的情况下有3!种排法,在前两位都确定的情况下有2!种排法…

由于字典排序是从小到大排列的,所以只需计算出第i位(从1开始)在它后面比它小的数的个数m,再用m*(n-i)!,遍历计算即可。

【参考答案】

www.jiuzhang.com/solutions/permutation-index/



作者:程风破浪会有时
链接:https://www.jianshu.com/p/582187cae8ab
來源:简书
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。