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

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

思路：函数先生成全排列，然后一个个遍历这个全排列，找到目标排列

代码;

 

class Solution {

public:

/**

* @param A an integer array

* @return a long integer

*/

long long permutationIndex(vector<int>& A) {

// Write your code here

// 找出A中每一个位置其后有多少个数比它小

// 然后再相加这些数与位对应的权

int len = A.size();

int c[len];

c[len - 1] = 0;// 最后一个数之后就没有比它小的数了

vector<int> a;

a.push_back(A[len - 1]);

for(int i = len - 2;i >= 0; --i){

auto iter = lower_bound(a.begin(), a.end(), A[i]);

c[i] = iter - a.begin();

a.insert(iter, A[i]);

}

long long ans = 1, fac = 1, cc = 1;

for(int i = len - 2;i >= 0; --i)

ans += (fac*=cc++) * c[i];

return ans;

}

};

截图：