我在InterviewBit上提到了“使用重复排序排列等级”的问题,除了长字符串值,我的解决方案可以产生正确的输出 . 这通常是由大因子的溢出引起的 .
我已经通过使用Java中的BigInteger数学类来解决这个问题,但解决方案提示建议使用“Modular Multiplicative Inverse”作为解决方法替代计算(N-1)! /(p1!* p2!* p3!...)其中p1,p2和p3是字符串中重复字符的频率 .
所以我的问题是,“Modular Multiplicative Inverse”如何帮助解决不适合整数原始类型的大因子值,以及它背后的数学直觉是什么?我知道如何解决这个编程问题,但阻止成功提交的唯一部分是长字符串值 .
非常感谢对此的任何解释!我的解决方案是在下面生成的,不使用BigInteger类 .
public class Solution {
public long fact(int n) {
return (n <= 1) ? 1 : (n * fact(n-1));
}
public HashMap<Character, Integer> generateFreq(ArrayList<Character> charList){
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < charList.size(); i++){
char c = charList.get(i);
if (!map.containsKey(c)) map.put(c, 1);
else map.put(c, map.get(c)+1);
}
return map;
}
public int findRank(String a) {
char[] charArray = a.toCharArray();
ArrayList<Character> charList = new ArrayList<Character>(charArray.length);
ArrayList<Character> sortedCharList = new ArrayList<Character>(charArray.length);
for (char c : charArray){
charList.add(c);
sortedCharList.add(c);
}
Collections.sort(sortedCharList);
long rank = 1;
int factNum = charArray.length - 1;
int matchedIndex = 0;
int index = 0;
while (!sortedCharList.isEmpty()){
char currChar = sortedCharList.get(index);
if (currChar != charList.get(matchedIndex)){
HashMap<Character, Integer> mapFreq = generateFreq(sortedCharList);
if (mapFreq.get(currChar) > 1){
mapFreq.put(currChar, mapFreq.get(currChar)-1);
}
long denom = 1;
for (char c : mapFreq.keySet()){
denom *= fact(mapFreq.get(c));
}
long factVal = fact(factNum); // prob: factVal overflows
rank += factVal/denom;
while (index < sortedCharList.size()){
if (sortedCharList.get(index) != currChar)break;
index++;
}
}
else {
sortedCharList.remove(index);
index = 0;
factNum--;
matchedIndex++;
}
}
return (int) rank %1000003;
}
}
1 回答
您在这里缺少的一个关键属性是,
我们可以使用上面的属性找到(factorial%MOD),这样它们就不会超过MOD值,因此不会超过整数限制 .
所以发现,(N-1)! /(p1!* p2!* p3!...)
模数乘法逆由下式给出,
再次找到没有溢出的模块化逆,您将需要使用模幂运算 . 你可以阅读它here .