lintcode刷题——排列序号

原题如下：

排列序号 

 描述 笔记  数据  评测

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

您在真实的面试中是否遇到过这个题？  Yes 样例

例如，排列 [1,2,4] 是第 1 个排列。

做题思路：

1、最笨的方法就是把所有的排列写出来，然后找出当前的排列是第几个，但是这种方法显然太过于复杂；

2、看到网上有一种很好的方法如下：对排列里面的每一个数，定义一个和排列等大的数组v，保存的是排列中的每一个数之后小于当前数的个数，然后当前的排列序号即为v中的每一个数和当前数在排列里面从后往前数第几位的阶乘的乘积，最后求和加1（因为排列序号从1开始）；

3、文字描述比较繁琐，例如：214，那么数组v中的数字为100，那么排列序号为1*2！+0*1！+0*0！+1=3，即为第三个排列。

具体的C++代码如下：

class Solution { public:     /**      * @param A an integer array      * @return a long integer      */         long long fac(int a) { if (a == 1) return 1; if (a == 0) return 0; else return a*fac(a - 1); } long long permutationIndex(vector<int>& A) { // Write your code here if (A.size() == 0) return 0; vector<int> v(A.size(), 0); int i, j; int count = 0; long long res = 1; for (i = 0; i<A.size(); i++) { for (j = i + 1; j<A.size(); j++) { if (A[j]<A[i]) { count++; } } v[i] = count;//每个数后面有多少个数小于它 count = 0; } for (i = 0; i<A.size(); i++) { int temp = A.size() - i - 1; res += fac(temp)*v[i]; } return res; } };