Index of Permutation II
给出一个可能包含重复数字的排列,求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。
样例
给出排列[1, 4, 2, 2],其编号为3。
Solution
这里需要考虑重复元素,有无重复元素最大的区别在于原来的1!, 2!, 3!...等需要除以重复元素个数的阶乘,颇有点高中排列组合题的味道。记录重复元素个数同样需要动态更新,引入哈希表这个万能的工具较为方便。
Complexity
时间复杂度 O(n2 ),空间复杂度 O(n)
Code
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;
}
}