# Permutation Index II ### Source - lintcode: [(198) Permutation Index II](http://www.lintcode.com/en/problem/permutation-index-ii/) ~~~ Given a permutation which may contain repeated numbers, find its index in all the permutations of these numbers, which are ordered in lexicographical order. The index begins at 1. Example Given the permutation [1, 4, 2, 2], return 3. ~~~ ### 題解 題 [Permutation Index](http://algorithm.yuanbin.me/zh-cn/exhaustive_search/permutation_index.html) 的擴展，這里需要考慮重復元素，有無重復元素最大的區別在于原來的`1!, 2!, 3!...`等需要除以重復元素個數的階乘，頗有點高中排列組合題的味道。記錄重復元素個數同樣需要動態更新，引入哈希表這個萬能的工具較為方便。 ### Python ~~~ class Solution: # @param {int[]} A an integer array # @return {long} a long integer def permutationIndexII(self, A): if A is None or len(A) == 0: return 0 index = 1 factor = 1 for i in xrange(len(A) - 1, -1, -1): hash_map = {A[i]: 1} rank = 0 for j in xrange(i + 1, len(A)): if A[j] in hash_map.keys(): hash_map[A[j]] += 1 else: hash_map[A[j]] = 1 # get rank if A[i] > A[j]: rank += 1 index += rank * factor / self.dupPerm(hash_map) factor *= (len(A) - i) return index def dupPerm(self, hash_map): if hash_map is None or len(hash_map) == 0: return 0 dup = 1 for val in hash_map.values(): dup *= self.factorial(val) return dup def factorial(self, n): r = 1 for i in xrange(1, n + 1): r *= i return r ~~~ ### C++ ~~~ class Solution { public: /** * @param A an integer array * @return a long integer */ long long permutationIndexII(vector<int>& A) { if (A.empty()) return 0; long long index = 1; long long factor = 1; for (int i = A.size() - 1; i >= 0; --i) { int rank = 0; unordered_map<int, int> hash; ++hash[A[i]]; for (int j = i + 1; j < A.size(); ++j) { ++hash[A[j]]; if (A[i] > A[j]) { ++rank; } } index += rank * factor / dupPerm(hash); factor *= (A.size() - i); } return index; } private: long long dupPerm(unordered_map<int, int> hash) { if (hash.empty()) return 1; long long dup = 1; for (auto it = hash.begin(); it != hash.end(); ++it) { dup *= fact(it->second); } return dup; } long long fact(int num) { long long val = 1; for (int i = 1; i <= num; ++i) { val *= i; } return val; } }; ~~~ ### Java ~~~ public class Solution { /** * @param A an integer array * @return a long integer */ public long permutationIndexII(int[] A) { if (A == null || A.length == 0) return 0; long index = 1; long factor = 1; for (int i = A.length - 1; i >= 0; i--) { HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); hash.put(A[i], 1); int rank = 0; for (int j = i + 1; j < A.length; j++) { if (hash.containsKey(A[j])) { hash.put(A[j], hash.get(A[j]) + 1); } else { hash.put(A[j], 1); } if (A[i] > A[j]) { rank++; } } index += rank * factor / dupPerm(hash); factor *= (A.length - i); } return index; } private long dupPerm(HashMap<Integer, Integer> hash) { if (hash == null || hash.isEmpty()) return 1; long dup = 1; for (int val : hash.values()) { dup *= fact(val); } return dup; } private long fact(int num) { long val = 1; for (int i = 1; i <= num; i++) { val *= i; } return val; } } ~~~ ### 源碼分析 在計算重復元素個數的階乘時需要注意`dup *= fact(val);`, 而不是`dup *= val;`. 對元素`A[i]`需要加入哈希表 - `hash.put(A[i], 1);`，設想一下`2, 2, 1, 1`的計算即可知。 ### 復雜度分析 雙重 for 循環，時間復雜度為 O(n2)O(n^2)O(n2), 使用了哈希表，空間復雜度為 O(n)O(n)O(n).