给出一个不含重复数字的排列，求这些数字的所有排列按字典序排序后该排列的编号。其中，编号从1开始。 样例： 例如，排列 [1,2,4] 是第 1 个排列。 思想： 直接计算。 例如：2，3，4，1 首先，另存到一个数组中，排序，再利用map，获得数字与位置的关系； 遍历数组A，在本例中，对于2，前面存在以1，开头的所有排列，个数为3！， 对于3，由于前面是2（注意要将出现在它前置位且比它小的数字去除），则也只存在2，1开头的排列，个数位2！，以此类推；
#ifndef C197_H #define C197_H #include<iostream> #include<vector> #include<map> #include<algorithm> using namespace std; class Solution { public: /* * @param A: An array of integers * @return: A long integer */ long long permutationIndex(vector<int> A) { // write your code here vector<int> v = A; map<int, int> m; sort(v.begin(), v.end()); int len = v.size(); for (int i = 0; i < len; ++i) { m[v[i]] = i; } long long count = 1; for (int i = 0; i < len; ++i) { int smal = 0; if (i != 0) { for (int j = 0; j < i; ++j) { if (A[j] < A[i]) smal++; } } count += (m[A[i]]-smal) * Recur(len - i - 1); } return count; } long long Recur(int a) { if (a == 0) return 1; return a*Recur(a - 1); } }; #endif