【題目描述】 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
來源：簡書
著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。
