题目：http://www.lintcode.com/zh-cn/problem/permutation-index/
给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。
样例
例如，排列[1,2,4]是第1个排列。
思路：
1.直接暴力，利用c++中<algorithm>中的next_permutation()方法不断的寻找下一个全排列，直到相等为止！
2.首先观察一个全排列， 例如：95412 = X
a.题目转换成按照字典序，这个全排列之前有多少个全排列。
b.X的前面的所有全排列中，对于位置1上可以是5, 4, 1, 2任意一个数，而且对应的全排列的基数都是4!个。
c.同理位置2, 3, 4, 5对应的基数分别是，3！，2！，1！，0！(0!==0)。
d.得到该位置对应的基数后，那么该位置对应多少个可变数字？9所在位置对应的可变数字的个数为4，分别是5,4,1,2；
5所在位置对应的可变数字是4,1,2；4所在位置对应的可变数字是1,2,；1所在位置的对应的可变数字:无。2所在位置
对应可变数也是无。
e.可以得到结论，X全排列某个位置上对应的可变数字的个数 == 这个数后面有多少个比它小的数的个数。
f.为了得到某个数后面有多少个比它小的数的个数，我们采用折半插入排序（从后向前插入）。
class Solution { public: /** * @param A an integer array * @return a long integer */ long long permutationIndex(vector<int>& A) { // Write your code here //阿欧，知道会超时，试一试还真tm超时 // vector<int> permu(A.begin(), A.end()); // sort(permu.begin(), permu.end()); // int cnt = 0; // do{ // int i; // for(i=0; i<A.size(); ++i) // if(A[i]!=permu[i]) // break; // ++cnt; // if(i>=A.size()) break; // }while(next_permutation(permu.begin(), permu.end())); // return cnt; vector<int> a; int len = A.size(); int cnt[len]; cnt[len-1] = 0; a.push_back(A[len-1]); for(int i=len-2; i>=0; --i){//统计每个数后面有多少个比它小的数的个数 vector<int>::iterator it = lower_bound(a.begin(), a.end(), A[i]); cnt[i] = it-a.begin(); a.insert(it, A[i]); } long long ans=1, fac=1, c=1;//基数fac从1开始 for(int i=len-2; i>=0; --i) ans += (fac*=c++)*cnt[i]; return ans; } };
