给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。 样例： 给出排列[1, 4, 2, 2]，其编号为3。
#ifndef C198_H #define C198_H #include<iostream> #include<vector> #include<algorithm> #include<map> using namespace std; class Solution { public: /** * @param A an integer array * @return a long integer */ long long permutationIndexII(vector<int>& A) { // Write your code here int len = A.size(); if (len <= 0) return 0; vector<int> v = A; map<int, int> dup; long long count=1; long long dupnum = 1; for (int k = len-1; k >=0; --k) { if (dup.find(A[k])!=dup.end()) { dup[A[k]]++; dupnum *= dup[A[k]]; } else { dup[A[k]] = 1; } int num = 0; for (int j = k+ 1; j < A.size(); j++) { if (A[j] < A[k]) { num++; } } count += num * Recur(len - k -1)/dupnum; } return count; } long long Recur(int a) { if (a == 0) return 1; return a*Recur(a - 1); } }; #endif